I have (had) the same problem for several projects. The only ones hit seem to be web projects. Deleting and recreating the profile solves the problem only once. Additionaly, comparing the publishxml generated yields no differences, so it does not seem related to the profile at all.
The workaround mentioned by OP to change build problems back and forth seems the only reliable solution at this time.