I don’t understand why some people are so surprised by this. Google has a long history of killing projects with little-to-no notice—and it doesn’t matter how big or popular it is (Google Reader, anyone?).
While Bit.ly is by far the most popular, it’s no better than Google or anyone else… they can sell or disappear at any moment, so the only permanent solution is to set up your own URL-shortener (which I’m told is not horribly difficult, but beyond the average user).