Also the test login in the amarok settings doesn't work.
Other third party programs like VLC work without problems. Also there are some amarok users where it still works without problems. (as you can see in the bug tracker there is one but he is a subscriber... )
Are there any information about recent API changes or server problems whatsoever?
I have the same problem on multiple machines. According to the entries in the above bug database of KDE/Amarok, the possible culprit has been found and a patch checked it. As there won't be a new 2.0.x release, we'll have to wait for Amarok 2.1 for the fix to become available - unless distributions pick this up.
amarok scrobbling problems (API changes, server issues?)