Router can't keep up with high speed connection ?

I've been using the same Linksys BEFSR41 router (4-port) router
connected to a cable modem and feeding three desktops and one
notebook since 2000 and never had a single problem.
Last week I upgraded my cable network account to a 10Mbit connection.
I was used to getting a 450 KiB/s speed with my basic cable and was
promised at least double that when I upgraded. Once I got my new
account I only got a marginal increase and was stuck at 540 KiB/s.
Tried a lot of settings, different times of day, etc... but 540 KiB/s
was like a brick wall I kept hitting.
Somebody suggested I remove my router from the cablemodem and hey
presto, speeds shot up to over 1000 KiB/s.

The Linksys has a capacity of 10 (WAN) and 100 (LAN) so I'm guessing I
found the culprit. I noticed that later models (BEFSR41 V3) have a
100/100 Wan-Lan setting, would getting one of these solve my problems?
I really want to keep my network setup (using a router) but would also
like to get the speed I'm paying a premium for...

I'm thinking of sticking with Linksys, but going after a model that
gives with higher speed and allows me also to also use my wifi laptop
next to my "wired" network (I am aware I'll never get the max speed
using wireless, but the rest of my network will still use good old UTP
cables)

Thanks for any suggestions/help

Norrin Radd