I have a Linksys router and run three computers with Windows XP Pro. No problem accessing Windows update.
The only time I couldn't get to Windows Update to scan on a new computer I had hooked up to the router turned out to be a screw up on my part. I had set the system clock to the right day and month but the year was off by one. Windows XP will not scan for updates if the system clock is off by 100 days or more.
Don't know if this will help but thought I would offer anyway.

Good luck.........Charlie