You might also want to try the Airport Express forum on Apple. I know you think it's not a problem with the network but a quick check there seemed to indicate that other Kindlers have had issues. So also worth a try.
http://discussions.apple.com/forum.j...D=1011&start=0