I am in the process of changing many of my category pages to static URLs with keywords in string. I do not want to lose the many links I have to these deep pages - will redirects from the old URLs be effective in keeping my links with Google, and is there any negative effect?
There will be no negative effect if you properly redirect each and every category and let Google know about this via Webmaster Control Tool and permanent redirection
The previous posters are correct. You should redirect your web pages with a 301 redirect of you want your new pages to get credit for inbound links to the old pages.