mvn release:prepare thinks tag already exists

I'm using Maven version 3.1.1 with Bamboo & Stash/Git. My Git-repository has the tags [project]-2.0.0 up to [project]-4.0.3. Running the build-/release-plan yields the following error:

build 28-Nov-2013 07:25:21 [ERROR] Failed to execute goal org.apache.maven.plugins:maven-release-plugin:2.3.2:prepare (default-cli) on project [project]: Unable to tag SCM
build 28-Nov-2013 07:25:21 [ERROR] Provider message:
build 28-Nov-2013 07:25:21 [ERROR] The git-tag command failed.
build 28-Nov-2013 07:25:21 [ERROR] Command output:
build 28-Nov-2013 07:25:21 [ERROR] fatal: tag '[project]-4.0.4' already exists

I checked roughly 12 times and I'm 100% sure, that the tag in question does not exist in the git-repository. Is this a bug or am I doing something wrong?