Sorry about that. Not sure how I missed that and taking you down a bunny trail.
If your Mac is unable to access the Express while connected to it directly using an Ethernet cable, then it may be best to go with your suggestion to use another Mac to administer it.
However, there must be a reason that your Mac's AirPort Utility cannot find the Express. One of the options with the AirPort Utility is to "Configure other..." By default, your Express will be configured to have an IP address of 10.0.1.1. Most likely your Linksys is using a default range of 192.168.x.x.
If you select the Configure other option and enter 10.0.1.1 for the address can the utility see it now?