How long ago did you subcribe to Spotify Premium? Does the desktop version of Spotify indicate you're using Spotify Premium (check where the title via the top of the interface)? Unfortunately, for whatever reason is going on with the Internet, subscription status updates takes a while for it to synchronize across all of your devices. You should also verify on your profile page if you have successfully subscribed to Spotify Premium, :).
If you'd like, you can still try out these alternative situations. Sometimes, your device may not want to ask for new information regarding your account. In order to force it to do this, you can try doing the following...
Log out of Spotify from your mobile device.
Delete Spotify from your mobile device.
Clear your device's cache (if applicable).
Reboot your mobile device completely.
Log back in.
You can also check out this topic (the same one Peter suggested) to see if any of the advice given here would be able to help you out, ^_^.
Lemme know if any of these solutions were of assistance to you, :).