Edit, 24 Nov 2016: this answer is apparently popular, so I am adding a note here. If you replace a tag on a central server, anyone who has the old tag—any clone of that central-server repository that already has the tag—could retain its old tag. So while this tells you how to do it, be really sure you want to do it. You'll need to get everyone who already has the "wrong" tag to delete their "wrong tag" and replace it with the new "right tag".
Testing in Git 2.10/2.11 shows that retaining the old tag is the default behavior for clients running git fetch, and updating is the default behavior for clients running git fetch --tags.
(Original answer follows.)
When you ask to push tags, git push --tags sends (along with any commits and other objects needed and any other ref updates from the push settings) to the remote an update request of the form new-sha1 refs/tags/name. (Well, it sends however many: one of those for each tag.)
The update request is modified by the remote to add an old-sha1 (or again, one for each tag), then delivered to the pre-receive and/or update hooks (whichever hooks exist on the remote). Those hooks can decide whether to allow or reject the tag create/delete/update.
The old-sha1 value is the all-zeros "null" SHA-1 if the tag is being created. The new-sha1 is the null SHA-1 if the tag is being deleted. Otherwise both SHA-1 values are real, valid values.
Even with no hooks, there's a sort of "built-in hook" that is also run: the remote will refuse to move a tag unless you use the "force" flag (though the "built-in hook" is always OK with both "add" and "delete"). The rejection message you're seeing is coming from this built-in hook. (Incidentally, this same built-in hook also rejects branch updates that are not fast-forwards.)1
But—here's one of the keys to understanding what's going on—the git push step has no idea whether the remote has that tag now, and if so, what SHA-1 value it has. It only says "here's my complete list of tags, along with their SHA-1 values". The remote compares the values and if there are additions and/or changes, runs the hooks on those. (For tags that are the same, it does nothing at all. For tags you don't have that they do, it also does nothing!)
If you delete the tag locally, then push, your push simply does not transfer the tag. The remote assumes no change should be made.
If you delete the tag locally, then create it pointing to a new place, then push, your push transfers the tag, and the remote sees this as a tag-change and rejects the change, unless it's a force-push.
Thus, you have two options:
The latter is possible via git push2 even though deleting the tag locally and pushing has no effect. Assuming the name of the remote is origin, and the tag you want it to delete is dev:
git push origin :refs/tags/dev
This asks the remote to delete the tag. The presence or absence of the tag dev in your local repository is irrelevant; this kind of push, with :remoteref as a refspec, is a pure-delete push.
The remote may or may not allow tag deletion (depending on any extra hooks added). If it allows the deletion, then the tag will be gone, and a second git push --tags, when you have a local dev tag pointing to some commit or annotated tag repo object, send your new dev tag. On the remote, dev will now be a newly created tag, so the remote will probably allow the push (again this depends on any extra hooks added).
The force-push is simpler. If you want to be sure not to update anything other than the tag, just tell git push to push only that one refspec:
git push --force origin refs/tags/dev:refs/tags/dev
(note: you don't need --tags if you're explicitly pushing just one tag ref-spec).
1Of course, the reason for this built-in hook is to help enforce the behavior that other users of that same remote-repo expect: that branches are not rewound, and tags do not move. If you force-push, you should let the other users know you are doing this, so that they can correct for it. Note that "tags don't move at all" is newly enforced by Git 1.8.2; previous versions would allow the tag to "move forward" in the commit graph, much like branch names. See the git 1.8.2 release notes.
2It's trivial if you can log in on the remote. Just go to the Git repository there and run git tag -d dev. Note that either way—deleting the tag on the remote, or using git push to delete it—there's a period of time when anyone who accesses the remote will find that the dev tag is missing. (They will continue to have their own old tag, if they already have it, and they might even push their old tag back up before you can push the new one.)