Regrettably, Karen, renumbering at least part of your project will be necessary. There's no support for changing element prefixes without renumbering, so the Tools / Renumber process is all we've got right now.
You can renumber your elements (and your prefixes are set) by both type and by package, so you don't necessarily have to do the entire project. If that's still too much to do all at once, you can actually move the necessary elements that need new ID prefixes into a temporary package all their own. Just set your new prefix, starting ID, etc. and you can "renumber" that temp package so you get your prefixes to line up how you'd like. Once you're done, you can then move them back to where they need to be.
Jason