Nokia BH-214 work flawlessly with my N900 (you'll need PR1.1, which I guess everyone has by now). Not sure how well the clip design would work for the gym though...

They're a modern BT 2.1 spec, which may bring some advantages in terms of good connectivity (see other threads on the subject).