Airport Express, OS 10.3.9 and Fios:WireLESS
Hi, Finally, after hours & hours, this worked: I didn't turn off the wifi on the FIOS Wireless Router but on my PowerBook (10.3.9 OS) I did the following: System Preferences~ Network~ Show Built in Ethernet~ Select TCP/IP, then configure iPv4: using DHCP. If you want to see the IP Address, Subnet Mask, etc. press PPP (next to TCP/IP). This is the same as kd_rome, and others' suggestions that i found, it's just that I couldn't find "Connection Sharing: (off)Bridge Mode" as I guess exists on Leopard and more advanced OS, which I should have!! And yes, I have an Ethernet cable running from the LAN on the ActionTec router to Airport Express (AE.)
I so hope that this helps SOMEONE so they can save themselves from the angst I put myself through!
Verizon had very few Mac people to help out at all and Apple tried but...
I have the FIOS Modem/Wireless Router and a Time Capsule, I turned off the wifi on the Modem and on Time Capsule under the Internet Tab I clicked on "connect using Ethernet-Configure IP4V using DHCP and Connection Sharing: (Off) Bridge Mode.
Then you have to run an Ethernet cable from one of the LAN port of the FIOS router to the WAN of the Time Capsule, or in your case, the AE.
Hope this helped!