I think many of you had the same Problem as me. Even if you've set the Autostart option to "off" Spotify would still start after a reboot of the device.
After a quick chat with the support team they finally brought a solution. After you changed the settings you have to log out and log in again. By doing this your settings get saved and Spotify won't start automaticaly
(sry for bad english I hope it helped)