Here's my take, a non-recursive version, at 66 characters:

sub a {
$_=shift;do{$_=join'',sort/./g;$i++}while($_=(reverse)-$_)!=495;$i
#23456789012345678901234567890123456789012345678901234567890123456
}
[download]

Update #1: Ah, by borrowing an idea from MeowChow's solution, I can shave off one character :-)

sub a {
$_=shift;do{$_=join'',sort/./g;$_=(reverse)-$_;$i++}until/495/;$i
#2345678901234567890123456789012345678901234567890123456789012345
}
[download]

Update #2: Changed shift to pop, another 2 characters off. Thanks srawls!

sub a {
$_=pop;do{$_=join'',sort/./g;$_=(reverse)-$_;$i++}until/495/;$i
#23456789012345678901234567890123456789012345678901234567890123
}
[download]

--ZZamboni