I know that a year passed since the last post, but I'd like to note about a workaround which work for me when I had a similar problem.
I didn't do any deactication or reinstallation or update (I use CS5.5).
So, the problem was the following:
I moved some AE projects and the links from PP project to them became broken.
However when I was asked by PP to enter new location of missing files, I got the message "Adobe Dynamic Link requires Adobe Production Premium".
The solution was the following:
for each broken AE link in the "Project Window" I did:
1) Right-Click -> Make Offline
2) Right-Click -> Edit Offline
3) Right-Click -> Link Media
and then chose the new path to the missing AE project.
Of course this requires manual work for each missing link, but if you don't have too many of them, it might be a good solution.
