Haven't heard this about Thunderbird 3, lots of moans about the
automatic settings wizard that kicks in when installed but not
freezing when getting mail.

You've tried removing TB3 but did you do it through Synaptic where you
have the option for complete removal ( i.e. all configuration files
relating to it too ).

After that, all I can suggest it trying another e-mail client and
seeing if that does the same - if so then the problem is in the e-mail
service itself or some setting it doesn't like.

Have you double checked all the settings compared to what is expected
by the provider ?

I have completely removed it and its config files.

I have tried Evolution - just last Sept, but its
just not as good at TB (for me) for how I work).

I download mail with fetchmail so its only going to my maildir to get
the bulk of my mail. The other half is imap from Gmail.

When I was using TB2 - I had a few troubles but never this type of
freezing.. its only been since moving to TB3 that Ive had it.

(note: 16 freezes in just typing out the above. Just TB3 froze - nothing
else).

I use Thunderbird with non of those problem either. You could try google
crome that has a smaller footprint.

Google chrome is not a mail client...........

Opera comes with a mail client and it is fast. I am not sure how well
it fits in with your email needs.
There is also Eudora: https://wiki.mozilla.org/Eudora_OSE
Zimbra: http://www.zimbra.com/products/desktop.html
Spicebird: http://www.spicebird.com/
Kmail in repositories
Balsa: in repositories
Squirrel Mail: in repositories
Claws: in repositories
Seamonkey: in repositories or from http://www.seamonkey-project.org/