I had both country regions set to Poland for Alexa and Music subscription. I've changed Alexa region to US temporarily but it didn't fix the issue. I cannot change my Music assignment without Customer Support.Wonder if changing your country set to a USA address might get round that, but that might screw up kindle library subscriptions for one thing (although you can move them back). That route is often used for Alexa users to point to the USA Alexa servers so they can get access to features other regions like the UK don't have.
Edit: on that same theme, do the entries for country in that setting match the country under Amazon Music account country/region under Your Music Subscriptions in your Amazon account? I feel there's a mismatch somewhere that's causing it not to work
It looks like @meszrum is absolutely right, our country is simply not supported for audio casting from Music to Alexa devices, although Alexa service is aware of our music subscription and can handle it correctly.