Comment 3 for bug 464283

Think I tracked my problem down to this:
Hamachi's binary is compressed with upx. You just need to uncompress it.

Good Luck Guys

note: /usr/bin is were hamachi's binary was on my computer.

sudo apt-get install upx-ucl
cd /usr/bin
sudo upx -d hamachi
Ultimate Packer for eXecutables
Copyright (C) 1996,1997,1998,1999,2000,2001,2002,2003,2004,2005, 2006,2007
UPX 3.01 Markus Oberhumer, Laszlo Molnar & John Reiser Jul 31st 2007

File size Ratio Format Name
-------------------- ------ ----------- -----------
830676 <- 331144 39.86% linux/386 hamachi

Unpacked 1 file.