Don't leave the users out to dry, just tell them to upgrade their site.

IMO, plugin and theme authors providing backward compatibility is one of the major reasons that people are not updating their sites.

I practice what I preach in this respect, BTW. The next version of Simple Facebook Connect will require WordPress 3.3. Backward compatibility will not be an option. The Simple Google Connect plugin I released today also requires 3.3 (beta works fine).