Yea, just get a router. P2P networking with Windows (or any platform I've tried) is a pain in the ass, I'm not sure why but I've never got it working reliably.
That said, there are a few things you can try. You've already got the workgroup names in sync and have run the network connection wizard on both, which is a good start. Try resetting your TCP/IP stack, I've seen this cause issues, instructions are at:
http://support.microsoft.com/kb/299357
If that doesn't work, can you ping one machine from the other? Try setting manual IP addresses on both (the one with the internet connection shared should already be manually on 192.168.0.1/255.255.255.0, so set the other to like 192.168.0.2/255.255.255.0 with 192.168.0.1 as the DNS server) - this doesn't always work but worth a try. If you can't even ping the other machine, check firewall settings (i.e. disable firewalls temporarily), and then consider checking your cabling, it _can_ go wrong.
But when a wireless + 4 port router is only £30, it's hardly worth the hassle