This was an interesting question. I see this in movie subtitles all the time when the English line is along the lines of, "sorry for your loss."
The "best answer" on this provides some more insight to the answer already given: http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q119850871
But the answer below that, where the guy talks about the origin in 江戸時代 is also interesting. Basically in summary between the two posts, it's the opposite of 気の薬, which in Edo times was something given to the sickly. I'd be curious to know just WHAT 気の薬 was (a drink? a food? a pill?). Since it was something good and given to cure sickness, poison (the opposite of medicine) was used to express something bad such as 不安 or 困ること. And today it's used to express sympathizing with someone for their loss.
To be honest, I still felt pretty unsatisfied with the answer, so I asked my fiancee (Japanese) just now, what the origin and original meaning of お気の毒に is, and she had no idea beyond that it's just a set phrase you say when to express sympathy for someone's loss.
To address your question about other uses, she was able to say that you indeed can say it to sick people expressing sympathy for their condition, IF the condition is light/curable/will get better soon. She said that you can't really say it to someone with a terminal or debilitating illness, because then it's kind of just reminding them of the crappy situation they're in. Whereas if someone breaks a bone or has a cold, well, they'll get better, and they're just down and out temporarily, so it's kind of like, "dang, that sucks that you got sick." Example sentence that I vaguely remember being told one time by a Japanese co-worker a few years ago: お気の毒に…こんな忙しい時期に風邪を引いちゃうって、最悪だね, expressing sympathy for the fact that I was sick, but I had my plate full and had to continue working anyway.
It can also be used somewhat sarcastically, but it's not that common. It will generally draw a chuckle if you use it for something like say, a close friend (definitely not a co-worker or someone you don't really know) lost their phone because it was their own fault/they were being a drunken idiot/etc.
