Genius feature doesn't work on iPhone
Refresh your Genius results in iTunes and then re-sync your phone with iTunes. Then you should be able to generate Genius playlists on your phone.

To refresh your Genius results:


Open iTunes
Sync your phone with iTunes so all your purchased music is in your current iTunes library.
Make sure Genius is on. If you select Store from the menu bar and it says "Turn off Genius" you're all set. Otherwise select Store -> Turn on Genius.
Now select Store -> Update Genius


iTunes will think for a while and eventually the status area at the top of the main window will say "Delivering your Genius results...".

When it's done delivering your Genius results sync your phone with iTunes. You should have Genius playlist capabilities on your phone now.