Figured I would make an actual thread here instead of piggybacking on others. Should cover all cases, too.
The HIB 64 bit Linux packages for Anomaly do not contain 64 bit versions of the game. They are 32 bit versions just packaged to say 64 bit.
If you are running a 64 bit Linux and you get an error like "No such file or directory" when trying to start the game, you probably don't have the 32 bit compatibility libraries for your system installed.
For Arch Linux, the "Problems running on Arch" thread has a list of the necessary packages to grab via pacman.
You'll need to google for any other distro's method for getting these libs installed.
Otherwise, the rest of us pure 64-bit schlubs will have to wait for a 64-bit package that really IS 64-bit.