Make sure that you run the 301 through a header checker and see a '301 moved permanently' header response as well as a new url and a 200 ok.
I did a 301 redirect from non-www to www in July. When I did a header check after that, the www was "200 OK" and the non-www was "301 Error". The header checker showed the Redirect Target as [www....] mysite.com (without the space).
I asked my webhost if the "301 Error" was correct and they said it was. Now that my pages have been dropping out of google, I'm beginning to wonder.
Here's what my web host did: 1. In Windows IS, created an entry for mysite.com (without www). 2. Pointed mysite.com to www.mysite.com as a 301 permanent redirect.