Just an idea. Maybe the key is automatically generated on the first publish. If that is the case, it may have an expiration date, say, one year after the initial build. If it is expired, perhaps that is what is causing the build to fail. Maybe try generating a new one? Though, the fact that you had the same problem when creating a new project suggests that the problem is something else. I imagine you'd get a new temporary key when building a new project (assuming it is in a new solution).
[
S<T>::f(U) // Out of line.
](http://msdn.microsoft.com/en-us/library/8yk3t00s(v=vs.71).aspx)