can I see a copy of your .htaccess file? You will need to add the 301 redirect before the perm rewrite. This might just be an issue with the order?
I'd do the 301 redirect with a rewrite rule instead like:
^product/original-url/?$ product/new-url [NC,L,R=301,QSA,T=application/x-httpd-php]