I'm kind of curious. Can you go to your "Control Panel" application, open "Bluetooth", tap on "Devices"? Highlight your headphone's entry in the menu and tap on "Edit".

What "Device type" and "Supported profiles" do you see listed?

My thinking: I know that I had this problem ONCE. I ended up trying to fix it by deleted the device from my list on my N800, telling the headphones to completely blow away its own list of recognized trusted devices (both of my bluetooth stereo headphones have this, so I assume they all must... check your headset's manual) and then re-introduced the headphones to my N800. It then correctly identified them as capable of HFP and HSP.