Embedded cover art not showing on Android phone

You could see this thread:
/t/9865/1

Or reduce the size even further to 200*200

As WMP mainly relies on the "folder.jpg" mechanism, it could be that the phone player also expects that file in the folder.

Also check if the tag version is any different (V2.4 vs. V2.3 which is the preferred one).

And: check the file consistency with Foobar or mp3val.