Spotify connect doesn't work between Windows PC and Android phone

[KentC93]

Plan

Free

Country

Poland

Device

PC, Xiaomi POCO F1

Operating System

Windows 10, Android 11 (Lineage OS 18)

My Question or Issue

After ditching MIUI in favor of Lineage OS, Spotify Connect stopped working - on the PC it shows "unavailable to control". It still works the other way around - I can control the desktop app from my phone. Is it because of the custom ROM installed?
I've tried: clearing all the data, reinstalling the app everywhere and also using "log off from every device" option in the account settings.

Edit: After updating to the latest Lineage OS - ver. 19.1 (Android 12) the issue still persists.