From the very start of the game on Xbox 360, I have never been able to recruit any followers that weren't part of a quest.
From everything I've seen on the internet, I've tried waiting, dying, and fast travelling. I have done these many times as I've been playing for many weeks so far.
For some reason, everyone says:
"It looks like you already have someone"
Also, I'm not sure about Lydia. She stays in my house in Whiterun, but doesn't follow me when I ask her to, and just says "An honor to see you, Thane" or something along those lines.
I haven't been able to find anyone who could fix this problem yet.