Finally, I've found what was causing the trouble: SQLite as Connection Database. It seems that Amarok stores every configuration parameter in a database - so every configuration change invokes long and lagging cooperation with SQLite. With other databases (like MySQL) it's way faster.
How to fix it:
- Go to Settings->Configure Amarok
- Switch to Collection tab
- Under Database choose MySQL:
- Specify your MySQL credentials. If you don't have MySQL server running on your machine you'll receive an error message like this:
- Press OK to save configuration
P.S. KDE 4 sucks.
P.P.S. I've switched to Gnome.