Click edit->preferences, and goto the importing tab. Change it to import as mp3 as default.
Now you can highlight the songs you want and right-click to be able to 'convert to mp3', which will convert your files. These should play.
However, your walkman phone will also play mp4 music files too, the default iTunes format, so i'm not sure that that's your problem. Are you sure you're putting the songs into the right place in your 'removable drive'? I have the Sony W810i walkman phone, and the files need to be put into a specific folder.