I fixed it for my repo by deleting the local tag and then doing a git fetch. This brought the updated tag.
Is there are "right" way to update tags that may have changed on the remote? This is a simple tag, not signed or anything, created with "git tag "
Make sure you fetch all the tags (through git fetch --tags), to get all the tags and not just ones referencing commits reachable from the branch heads.
Those (fetched) tags are annotated ones (and usually not lightweight), and if you add deleted one on the local repo, they will just pop back after the fetch.
However, if you have deleted a lightweight one, then you need to recreate it locally: a lightweight tag isn't usually pushed or fetched to/from a remote repo.
Note that starting git 1.9/2.0 (Q1 2014), git fetch --tags will fetch everything (like git fetch), plus the tags. See "Does “git fetch --tags” include “git fetch”?".
Again, fetch "everything" means annotated and lightweight (if those lightweight tags were previously pushed).
As noted below in biocyberman's answer, if you want to fetch tags from all remotes (not just the default remote named 'origin'), you need to add the --all option.
git fetch --tags --all