I was fooling around with my e61 and a motorola hs500 headset, and managed to get music from the built in mp3 to play through the headset, does this mean it has the profile or not?

It depends on whether it played in mono (same channels through both earpieces/speakers) or stereo (different channels through the left than through the right earpiece).

As far as I know, the E61 does not support Bluetooth stereo sound.

does anyone have a stereo heaset in nyc I can try with it;-)