It hasn't been updated in two years. It does not work on 64-bit Linux. There's a getlibs hack to make it work for Debian/Ubuntu 64-bit, but even that doesn't work with the release of Ubuntu 11.04 because the obsolete 32-bit libraries it links to are no longer in the repositories.
Why release something and then not support it?
For anyone else having the same problem: The Banshee Amazon plugin by Aaron Bockover works fine.