[Edit, April 2017] If you made your original clone with --single-branch, your remote.origin.fetch setting will be the problem. If you used a --depth limit, that too implies --single-branch. Restore the normal remote.origin.fetch value described below and you will get a fuller clone.
Normally, just running git fetch should restore your remote-tracking branches.
If git fetch is not restoring them, then I wonder: what goes git config --get-all remote.origin.fetch print? (This assumes the remote is named origin; if not, substitute the actual name.) It should be set to +refs/heads/*:refs/remotes/origin/* (again assuming the name origin). Special cases (such as fetching notes) might add more lines.