This seems to get lost in multiple threads so ill post it here.

Go to https://www.spotify.com/uk/account/profile/  and look under Country.  Youll notice a link to edit payment info.

Other countries that are not the United Kingdom can just go to their specific region site and click their profile.

Click the link and go to the page. Remove the current Info and click change. Now you can add the new one or change the info..

It seems theres a bug that is stopping people from getting to this link from the subscriptions page, so this is a workaround.

Please note.

This can also be used to cancel your paid account. SImply remove all payment info and click change. Since there is now no payment information registered to your account, your account will automatically switch to "Free" status on your supossed billing date.