I also use a router, with no problems.
Just a shot in the dark but make sure in “Settings”> Updates> Update Paremeters, do you have “My Computer is directly connected to the Internet” check boxed?
This may help. :-\