@aakk9999 the site does currently link to the new versions of the urls without the special character. The way oursite is set up you can have example.com/productx/cat/124 and no matter if you enter something like example.com/prx/cat/124 it will auto redirect back to example.com/productx/cat/124. This is the way the system was set up so the urls 301s should have been instant when the special characters were removed.
It could be a case of Google needing to recrawl the pages in order to get this updated, I will have to let you know as it goes on, often it takes a long time for the duplicate title tag error to remove itself from webmaster tools though.
As I have been pouring over the answers and what to do, I think i am going to have to bite the bullet and leave the new urls in place. They are almost all indexed now with the new url and im afraid of what will happen if i 301 them back again, seems like Google would hate this back and forth. Also we are a small company so the dev time to unwrite the removal of special characters (and hoping it creates the old urls again) seems like it may take to much of the developers time away from other projects he is working on for us.
Let me know if you think that i absolutely should change them back and then I will atleast look into it further. Thanks for all the great help on this question @tedster, @kellyman and @aakk9999