I am also experiencing this problem. I have just recently signed up for a spotify premium account and have downloaded the Spotify App for my Samsung Galaxy S3 from the Google Play store. I have searched the forums and troubleshooting guides and have yet to find any viable solution to my problem.
Here is the Problem-Template from the Troubleshooting section, just in case that helps:
Description
When attempting to log into Spotify via Facebook on my Android Phone
(Samsung Galaxy SIII, German Version of the App) I am automatically
sent back to the opening screen. Occasionally I see an error message
to report error #1118578.
What are the steps you took to get to the error/issue?
1) Open Spotify on Android
2) tap "Melde dich hier an"
3) tap "Mit Facebook Anmelden"
What I expected to happen
Successful Login
Did you restart your device when troubleshooting in section B?
Yes
Did you read the connection troubleshooting tips?
Yes
Your device
Samsung Galaxy SIII
Device’s Operating System
Andriod 4.1.2
What type of account do you have?
Premium
(FYI for the below points: Android devices tend to refer to the internal memory as "SD Card" and the SD card you inserted yourself as "External SD Card")
Space left on your device
8,37 GB of 11,1 GB
Space left on your SD card (if applicable)
see "Device"
Space left on your External SD card (if applicable)
4,06 GB of 15,0 GB
Is your device rooted?
No
Are you using a custom ROM, if so which one, exactly?
No
Did you set your external SD card as storage location?
No
Did you manually install an older version before installing the latest version from the Play Store?
No
Do you have the same issue when switching between WiFi/Mobile Data (If applicable)?
Yes
If you said "No", when does the issue not occur?
N/A
My mobile Spotify version
0.5.11.4
My desktop Spotify version (if applicable)
0..8.8.450.gd9413516
My mobile provider and country
T-Mobile (Germany)
My username
1168971488
Do you have a Spotify (non-Facebook) login?
No
Are you logging in with Facebook or with your Spotify login details?
Facebook
Do you have any screenshots you can attach to more clearly explain your issue?
In Progress