I have a build set up in Teamcity that builds and tests a mercurial branch, and should then tag that branch.
The building works correctly but when it comes to labelling it fails with the error "push creates new remote heads on branch 'default'". I find this slightly odd because the branch that is being used is not called default.
In Mercurial, hg tag creates a changeset that updates .hgtags. It sounds like your working parent is not a branch head, so hg tag will create a branch, and new branch heads can't be pushed by default. Just a guess...post an example script that illustrates the problem.
You can pull the remote repository and look with hg heads which heads are there, who created them, and if you want to merge them.
Although I can't be sure how teamcity ended up with multiple heads, perhaps there was a checkin while teamcity was performing the build, It did end up with multiple heads. Because it reuses the same mercurial directory each time every time it tried to push ended up failing. The solution was to delete all directories in the mercurial cache directory, as set up on the Version control settings page. Then restart teamcity. This gave a clean diretcory and everything worked as planned.
This happened to us when TeamCity attempted to check in the tag change to mercurial but failed due to a change in the account it used for checkout/check-ins. TeamCity does not know how to merge changesets so it simply keeps downloading the new changesets, building, then trying to check the un-merged changeset in which gives the error you saw.
Deleting the cache off the buildserver is the easiest way to recover.