Hello Brian,
I tested PSK31 both ways from Fldigi to AndFlmsg and reverse, with and without RSID. I tried two Samsung and one Oppo phone and they all worked here.
The only thing I can think of is a large difference in audio clocks. The test would be to use RSID with PSK31 (automatic on Android but may need to be enabled on PC) and see how large the deviation is.
On my phone to Laptop I get one to four Hertz depending on the devices (1496Hz and 1499Hz decoded when sent at 1500 Hz).
The only thing is that it does not explain why you would decode PSK31 sent I presume from the same device, but from another app.
I am puzzled.
One option for looking further into this would be to send me a recording (use the Fldigi recording to wav file feature) of a short text send from your device to your Laptop/PC. You can send it directly to my email address wihich <myCallSign> at gmail dot com.
All the best,
73, John (VK2ETA)