It depends on what yo umean by a "shared" connection
I have 2 PCs plugged into a single router, which is setup for my internet connection, so they can both access the net at the same time using the router.
Seems like only one PC had managed to aquire this trojan (or whatever it was that had added the registry keys to redirect from Google) but it was making the other PC do the same, even though the other PC didn't have the registry changes.
Very odd. At least next time I'll know what to do, although both PCs are now loaded-up with anti-virus and anti-spyware programs. I see that Spybot has settings to automatically protect against these redirects, which is nice.