I resolved this issue for myself, incase you haven't been able to fix it by now.
Unfortunately I don't know what actually fixed it, but here's what I did (in order). It was most likely either 6 or 7, I'd suggest starting save time but I'm including 1 - 5 incase it's a combination of one of them with 6 and/or 7:
1) fiddling with the settings for a few days. Turning off the "share my listening activity" and "show my recently played artists" and "private session", listening to some albums, then turning it back on.
2) logged out of everything - my phone, tablet, desktop app and web browser.
3) uninstalled and reinstalled app on my desktop.
4) played music on all my devices. Phone, Kindle, web browsers (firefox and microsoft edge), desktop app
5) tried another free account on all these devices and Recently Played Artists started updating again. Confirming it probably wasn't the device.
- None of those things alone fixed it, so it's likely one of these 2:
6) I reset my password
7) I went to my account overview on the Spotify website, and on the left menu at the bottom of the list is a tab called "Apps" with a puzzle piece icon. It's all the Apps that I gave permission to access to my Spotify account.
- the app permissions I REMOVED were:
a) a 3rd party app called Swarm.fm that I used to use for more in depth new releases. I think it was this one because I removed it from my bookmark toolbar around the same time I started having issues. I don't know if that makes any sense, but it's one **bleep** of a coincidence if not.
b) Something about "allows the profile service to transcode images". I apoligize, I don't remember the actual name of it and I have no clue what it was.
- and the app permissions I KEPT were:
c) Spotify Advertising Cookie
d) Spotify Community
e) Spotify Mobile Web Player.
Voila, my Recently Played Artists began updating again. quicker Than before too (used to take up to 8 hours, now 10 minutes)