Make sure that any firewalls or antivirus programs you have installed are not blocking Spotify. If you find that one is then unblock Spotify and reboot computer. If not or if you are still having same problem, proceed to next step.
Change Programs on Startup
1. Start Task Manager
Via the taskbar. Right-click an empty area of the taskbar and choose Task Manager from the pop-up menu that appears.
Via the new power user menu. Open the power user menu—WINKEY + X, or move the mouse cursor into the lower left corner of the screen and right-click—and choose Task Manager from the list of options.
Via Start search. Tap WINKEY, type task and then hit Enter.
By default Task Manager runs in a new compact mode.
2. To expand the display and find the startup application management functionality, select More details.
3. Then, select the Startup tab. This view shows all of the applications that are configured to run when the system boots.
4. Enable anything related to Spotify (I'm not sure how it looks on your side). They might be listed as :
So I've tried 'Booting Spotify Offline And Minimizing Memory', and that worked one time, but after that the same problem was there again. Also deleted spotify with CCleaner and used the fix register tool but that too didn't work out. This is so weird.. And really anoying.