On Android -> Wifi details there is a privacy option, Use randomized MAC/Use device MAC. Switching to Use device MAC worked for me.