jjjaded , what i could suggest is to try installing another version of MP3 Utilities and see if the formatting could be done properly.
Also, try using another USB cable as some stock cables are known to be faulty.
As the last alternative, you can try using HP Format Tool to format the player directly.
http://www.mympxplayer.org/hp-format-tool-df466.html