Removing the plugin 404 errors

I deactivated the plugin changed my theme and installed another pagination plugin. I got a message from the Google Webmaster too;s regarding an increase in 404 errors. It seems that removing your pagination plugin caused this. How do I solve this? Do I have to stay with you plugin forever to avoid this?

http://ww.wp.xz.cn/extend/plugins/wp-page-numbers/