We've tried Gamespy, Hamachi (LAN) and direct IP. With direct IP he could see my game but he could not join it... I figure it might be a port issue..?
Hard to tell without details, but sounds like a firewall and/or port issue. SFC is sensative to anything firewall, software or hardware, even ISPs, so start with ports, make sure btw that the ports are forwarding to your computers IP, if your on DHCP then there is a chance your IP would have changed from the forwarded IP. Switch to static if possible (if you havent already), as well be sure no firewall is "secretly" running, a lot love to still run even if you tell them to stop requring them to be killed manually.
One final note for now, I havent had much success on getting Hamachi to work in SFC, though I should say Ive only had the time to do very very limited testing with it, I'd suspect if any VPN would work it would need to manually be setup.