Skyrim "You already have a follower" issue

If you have become Thane of a hold you will be granted a housecarl which would count as a follower. If you have a house go there and leave them.

I had this same problem, I had hired one of the mercenaries who followed me around for a few missions then randomly disappeared. All the other followers i tried to recruit told me I already had someone with me.

The only thing that fixed it was starting a mission that automatically fast-travels you somewhere or otherwise changes your position on the map. I used the mission where you call Ohdaving. I talked to the Jarl of Whiterun sitting on his throne inside, then we automatically travelled out to the Dragonsreach porch. When I appeared out there, my follower was somehow standing right next to me as if nothing had ever happened. I assume the same thing would happen on any other mission where you automatically travel to somewhere else on the map. The game re-setting your position seems to do the same thing for the follower.