I am considering buying AT&T VOIP for home.  I have a wireless network
and want to make sure X-box Live will work with this new set up.

I am looking for a YES or NO answer on system compatibility. If the
answer is no, why and what comparable routers would work.

AT&T provides the a LinkSys RT41P2-AT router.  It does not have
wireless component, so I am looking to buy the LinkSys WRT54G
Broadband Router and the LinkSys WAP54G Wireless Access Point.

The configuration would look like this.

DSL modem --> RT41P2-AT --> WRT54G --> Wireless --> WAP54G --> X-box.

I understand that compatibility has something to do with ICMP and MTU
setting, but I am not clear weather these routers have the appropriate
support for the settings required by Xbox Live.

I am in IT and fairly technical, so if a follow up question is
required, I should be able to provide a technical explanation.

Thank you in advance.

Yes it will work but I don't know why your going with AT&T.  Lingo.Com
is cheaper and from my experience just as good as AT&T.  The Lingo.com
router will work exactly as you have planed.