Thought I would throw my 2p in here.
My brother has just installed a Buffalo NAS on his office network. He's now looking at off-site backups, so that should the office burn down, at least he still has all his business documents elsewhere (many hundreds of miles away).
My first hurdle was to get the VPS he has (a small Linux virtual private server, nothing too beefy) to dial-in as a VPN user to his broadband router (he's using a DrayTek for this) so that it itself can be part of his VPN, and so it can then can access the NAS directly, in a secure fashion. Got that sorted and working brilliantly.
The next problem was then transferring the files from the NAS to the VPS server. I started off by doing a Samba mount and ran into exactly the same (or even worse) issue that you've described. I did a dry-run rsync and it took over 1 hour 30 mins just to work out what files it was going to transfer, because as Evan says, under this method, the other end isn't rsync so it has to do many filing system calls/reads on the Samba mount (across a PPTP/tunnelled connection, with a round trip time of about 40ms). Completely unworkable.
Little did I know that the Buffalo actually runs an rsync daemon so, using that instead, the entire dry-run takes only 1 minute 30 seconds for 87k files totalling 50Gb. Obviously, to transfer 50Gb of files (from a NAS that is on a broadband link with only 100k/sec outbound bandwidth) is another matter entirely (this will take several days) but, once the initial rsync is complete, any incremental backups should be grease lightening (his data is not going to change much on a daily basis).
My suggestion is use a decent NAS, that supports rsync, for the reasons Evan has said above. It will solve all your problems.