I would recommend giving Cliemail a miss and purchase Snappermail www.snappermail.com
You should be able to find info on settings for your phone and service provider at www.esato.com
I'm with O2 and found everything I needed there after spending weeks arguing with people at O2 that didn't have a clue.
It is a pain to set up but well worth it in the end and Snapper is a brilliant app.
Agreed on Snapper - thelatest version with seperate folders for each isp is excellent and integrates well with Quick office for reviewing and editing word and excel files.