Well i have some kind of 'issue' with this too.
When i connect any headphones other than the stock ones that came with it, it doesn't show up in the notification bar (no headphone icon is appearing).
However, the headphones are working perfectly fine.
The problem i have isn't such a big deal, because they are working anyway.
I reckon any 3.5mm headphones should work, i have no idea what could possibly cause your problem.
I use skullcandy's on it btw, but they are just cheap headphones with bad sound quality :P