Hamachi was giving us problems, I have no idea why but if I were to guess I'd say it's a combination of routers and windows 7.
Anyways, there's an easy alternative that requires considerably less effort. It's called Shadowflare's server.
Download Hercanic's STF here,
http://stf.campaigncreations.org/Downloads/Mod/STF_1151_0059.zip
Unrar.
Run the registry file called "private servers" or somesuch. Say "yes" in the dialog that asks to add this to the registry.
Run the mod of your choice, or even regular starcraft. SF's server accepts any version.
Go to the multiplayer menu and select "Shadowflare" in the realm list.
Connect, make your account, enjoy.
I think the server does need a port opened, so if you're using a router, then yeah. But plenty of people use it without any problems so I don't see why you guys would have any.