I recently ran into an issue where Google search results took clients to the restricted index - you know, the page that tells them "The page you are trying to view is restricted".
The issue turned out to be variance in the categories ID's. Not entirely unexpected, but certainly not desired either.
The short term answer would seem to be a 301 redirect to the new category URL.
David