A lot of people had this problem, and it was well reported on Apple.com's official user forums, you can easily do a search there to take a look.
The thing that seems to have solved it were the base station (firmware?) updates. Are you using the most updated versions, and the latest OS X?
If you have further difficulties, I would check the Apple.com user forums, as there are several very knowledgeable folks in the base station area.
Also the old graphite ABSs were known to blow a capacitor, so there's a way to replace that as well (again, in Apple forums).
The AEBS that you ask about has one really major fault IMHO: It can only have 20 entries for port mapping, which is utterly ridiculous. I've also found the range to be shorter than, say, a netgear router (so I would buy the one with the useless modem and the useful antenna port).
The AEBS only having one ethernet in is really a disadvantage too, although the built-in USB printer port is very nice-- although PC routers seem cheaper, if you look for business models which have the built-in USB port, the price starts to look more comaprable (although of course these would have more ethernet ports).
Also, I've found the Airport Admin utility can be difficult to use at times-- it's hard to see who is connected to you at any time, and setting security with a mixed pc/apple environment can take longer than it should (since it tries to keep the hex side of things invisible).
Of course, if compatibility with all features of the airport express is an issue, by all means get the AEBS, and not a pc router.