Page Not Found errors

I'm suddenly witnessing Page not found errors in the following instances, since after upgrading vBSEO.


1. A new user signs up - and recieves and authentication email from the forum. When he clicks on the links provided, it gives him an error saying that the page was not found.


2. A user recieves a private message notification - as a pop-up. When clicked, it too results in a page not found error.

What can possibly be the cause of such errors? Does this have anything to do with vBSEO?


P.S.
Mind you, not all users are facing this issue. It's quite random.

What are example URLs in both cases?