"Airport Utility unable to find your Airport after restarting"

Welcome to the discussions, Mick!

When the AirPort Express is having difficulties joining a wireless network, the problems can almost always be narrowed down to two possibilities:

1) Non compatible Radio Mode

2) Non compatible Security settings

Please perform a quick test by temporarily powering down the AirPort Express (n) and then also turn off the security on the AirPort Extreme.

You can do this by opening AirPort Utility - Manual Setup
Click the Wireless tab below the row of icons
Locate the setting for Security and jot that down, then set it to None
Update to save settings

See if one of your AirPort Express(g) devices can be configured to join the network using no security. If the Express joins successfully, you know two things:

1) The Radio Mode is compatible since the Express would not join otherwise

2) You have a Security setting issue on your network

If the AirPort Express will not join the network with no security, this tells you that:

The Radio Mode setting that you have on the AirPort Extreme is not compatible with the capabilities of the Express (g)

Turn the Security on the AirPort Extreme back to the setting that you had before the "test".

Please post back with your results.

What type of Security setting are you using on the AirPort Extreme?

If you are using WPA2 Personal now, you may need to switch to WPA/WPA2 Personal and then use the same setting on the AirPort Express devices.

Try holding down the option key on your Mac while you click on the Security setting drop down box to display all of the choices here.

Glad you got things going.