You'll need to upload a new version, if only to add some text to the docs to say that it's deprecated.

I would also make the module spit out warnings when used (which the user could turn off) and then remove it from the CPAN after a year or so. It would also be neighbourly to notify any other CPAN authors who have dependencies on your module - you can hunt them down through this page.