I have a problem with this - it only happens on certain albums, so perhaps they have something in common. The one playing currently is from Magnatune, album name Rain Trip, musician Toni Iniguez. Perhaps someone could test whether this album gives them problems too.

What happens is that I get the popup announcing the next track, but it doesn't start playing. The Play/Pause button is displaying Pause. I have to Stop then Play for each track.

This is a bug with your Phonon backend. Try different backends - VLC, GStreamer and Xine are available. Xine is no longer maintained, but both VLC and GStreamer should work. May be packaged as phonon-vlc or phonon-backend-vlc depending on distro.
You can select which is used from the list of installed backends in System Settings > Multimedia > Phonon > Backend. Note that Amarok will crash if you try and switch backend while it's running.

OK - I've been using gstreamer, but I'll try VLC. Amarok seems to have been very unstable lately. Fingers crossed that this cures it.

I can confirm that advancing tracks is working correctly with VLC backend. Thanks for the tip.

I believe this is a known issue with older versions of the GStreamer backend. It should be fixed now, so I guess you're waiting for distro availability. I don't recall which release it went into, but if it was the most recent, that was only a few days ago.
We usually recommend VLC over GStreamer anyway.