I used to run into that with my old Linksys router. It's definitely a problem with how the router handles the packets because - assuming it's the same issue - if you plug directly into the connection without the router, you don't get the error. That said, the only thing that fixed it for me was a firmware update for the router so you might look into that.
im running the latest firmware...im so tempted to get a wrt54g right now ...so i can play..aHHHhg