It seems to be an issue with Android 4.0.4. I tried 2 devices (a RAZR and a Galaxy) and they both showed the BT A PAUSED error described above. I then tried a A500 tablet running 4.0.3 and it worked fine. Other "strange" thing I noticed, the 4.0.4 shows 00:00 frozen while playing and the 4.0.3 does not, it's just blank (which I think is better than the frozen 00:00, but I think a working counter would be the best).
Going to try Alpine support, but I assume since the 4.0.4 was just released at the end of March and hasn't been rolled out to a majority of handsets that this is hopefully being worked on.....