try doing "store -> update genius" from the menu
also, your songs must be tagged correctly, at least artist and title
and if it's something obscure, it may or may not show up apple's genius database.
---
edit
just realized you're on iOS.
are all the songs actually on your phone? or available via iTunes match? I'm not sure how genius works with songs that haven't been downloaded to your phone.
you could still try updating the genius database on your computer