Usually this is a firewall of some sort. When hamachi fails, that is almost certainly a software firewall on one or both of your machines. First thing to check is that both of you have the same port set in the settings window.
Then, you will want to look at you various firewalls and make sure that the udp port used (not tcp!) is open on any and all of them. You may also need to make sure that aiwar.exe is allowed as both a client and server in your firewall.
Common firewalls: windows firewall, which is on most machines possibly in addition to others; zonealarm or other firewall-specific products; norton or mcafee security products, or similar, which may in include firewalls you are not aware of.
To test, often it is fastest to temporarily turn off any firewalls you have, verify that the game works, and then turn back on the firewalls and add the needed allow/exception rules.
