Took me a while to figure it out. Whilst Twitter itself allows you to upload .JPG, .BMP or .PNG pictures, for some reason, twitter clients only like .JPG files.
If you or someone you know is having this problem, simply go here - http://twitter.com/settings/profile and change your picture to .JPG
If you do not know how to convert your picture, the easiest way is to go to your Twitter page and download your big profile picture, then use a service such as this that will do it for you or alternatively, open it in Paint (or any image editor) and choose save as, and choose .JPG image.
Now upload this new image, and it should be fixed!
In Tweetdeck (possibly others), your picture is drawn as and when you Tweet, you will only see the picture from this point on and not for previous tweets.
Many thanks to @Blowdart for telling me that I was one of the people who had this - I simply had no idea and not sure how anyone would know that they are affected unless someone has told them.