I don't have the same setup as you, but I do have Airplay to a non Apple device.
I have an iPad, and a Minix X8 with XBMC, and XBMC has built in support for Airplay.
It is not something I use very frequently, but I fired up Spotify and enabled it to stream over Airplay, and it worked perfectly.
Some things to look for is if they are on the same network, in my setup both were connected to the 2.4GHz Wifi.
I don't think UPNP is used for the internal network, but try to enable it to see if this does any difference.
Also note that some firmwares have trouble with Apple devices and the 5GHz network, so try and connect your devices using the 2.4GHz network.