You have to enable Spotify under Game Activity after you have connected your accounts.
So, if it isn't listed under 'Added Games', its not going to show up as your Discord status. to add Spotify click the cog in the lower left, go to Game Activity, click Add It! under the section that says "no game activity detected", type in Spotify and click the first option. enable or disable the overlay and make sure the "Display currently running game..." is enabled.
In your User Setting on Discord, under Connections, is "Display Spotify as your status" enabled? And, I'm not sure if this actually is your problem, but in your Spotify settings on the device you are listening on, in your settings under "Social", is "Share my listening activity on Spotify" enabled? Also, check to make sure that you aren't running any games that would take precident in your status over Spotify. Running Spotify and Discord on the same machine may also help. The more information you share, the better