All of my url's recently changed because I'm now using a component for search engine friendly url's for Joomla. But all my pages indexed by Google are my old url's which lead to 404 pages. What's the best way for those old url's to go away and my new url's to be indexed?
I'd have to agree, 301 redirect old URLs to the new ones is your only chance to save your current SERPs and Pagerank value, it will still take time before it all transfers over.
What about removing the bad url's in Google webmaster tools and setting the Googlebot crawl speed to fast for a little while?