Amazon.com has changed their data API to require that all searches be signed with a secret key, unique to each user. Tellico 2.0 for KDE4 supports the new method. However, most older versions (i.e. all versions of Tellico prior to 1.3.6) do not.
A quick backport of the fix was made for Tellico 1.3.6 for KDE3. Most distributions probably won’t package it, since they’ve moved on to KDE4. Find it on the Download Page.