I am not sure if you got it right:
UTF-16 is written for the V2.3 standard.
UTF-8 is written for the V2.4 standard.
There is not UTF-16 for V2.4.
And as these 2 standards represent a different approach to writing the tags. The WIndows Explorer, e.g., does not read V2.4 tags alltogether.
So it could be that your mobile cannot cope with V2.4 tags...
I would return to V2.3 tags.
There is also a thread in the FAQs on strange displays: /t/2785/1
The solution to use iTunes for tagging is weird as iTunes very often does not really tag files but writes data only into its database. I wouldn't do it.
Edit: to make sure that your files are ok you should use mp3val and mp3diags to check their integrity - to find out that the hicups do have their origin in some corruption.