Ayuda sobre bitrate en un reproductor MP3

Necesitaba un MP3 para mis largas sesiones de ejercicio diarias, e informandome por aqui vi que mucha gente recomendaba el Creative Zen Stone Plus de 1 o 2 gb por su precio y su calidad de sonido.

La decision ya esta practicamente hecha, pero necesito saber mas o menos cuanto tiempo de musica podre meter en esos 2 gb. Quiero decir, que recodificaria todos mis MP3 a una calidad menor, si procede, para que quepan mas canciones. La pregunta es, mas bien:

A que Bitrate se empieza a notar un bajon de calidad en los MP3? Alguien ha probado diferentes calidades, para dar con una buena solucion?

P.D Tengo unos Sennheiser PX100, que creo yo que no me daran problemas en ese sentido