Edit History

As a first step, did you refresh the rewrite rules? Shop Parameters -> Traffic & SEO under 'Set up URLs'

You could also try toggling friendly urls off (save) and on (save) again.

(And for good measure clear the cache)