I created my account in November of last year via Facebook, from the moment I finished signing up I have this username, a bunch of random numbers and letters.
Since then I have unlinked Facebook, I have linked it again and despite that my username does not change.
I also tried creating a new account but had the same issue, the username I defined ended up changing to a random string (Via facebook or not).
Solved! Go to Solution.
After contacting support I managed to solve it:
Go to your account: https://www.spotify.com/us/account/overview/
Then Privacy Settings > Enable 'Process my Facebook data' (Renable it if already enabled)
Inside the app connect to Facebook (Again: Reconnect if already connected)
Then wait 24 to 48 hours until your username is updated and an additional 24hrs until it gets indexed in the search bar.