@Flagg1982:
nd people in Fushia didn't treat him like he was anything special.
And Shanks didn't ACT like anyone special. He let low class weaklings toss drinks on him because… he would have felt bad about horribly hosing them.
And, he already had his entire crew assembled.
@Urouge:
Sure, he probably had world famous status, already. That doesn't automatically mean that he was an Emperor, though. He certainly wasn't ruling over the New World at the time.
One way or another, Mihawk got from the Baratie to… WHEREVER Shanks was to tell him about Luffy's first bounty pretty quickly. Within a couple days. On his little tiny raft. Its possible Shanks had been chilling in the weaker oceans.
(And just as possible that Mihawk moseyed along, being a shichi, he should have the authority to cross the red line at will)
Though given the fuss about "Shanks meeting whitebeard" it does seem pretty likely that him crossing the line would have been news, even if it was incognito through the fishman island route, so I guess he hasn't crossed the barrier lately. Because of that it's most likely Shanks has been in the New World for a while, but its not a set-in-stone sort of thing.
Really, its hard to gauge since the entire OP story has only taken about a year at this point.
It boils down to, was Shanks always a big shot and the people of Fushia just didn't know it? Or was he an up-and-comer hanging out in the weakest blue for the lulz, who then went and became big time?
PROBABLY the later, but there's nothing fully dismissing the idea that he might have been a yankou back in the day. (I agree that he probably got the title later though.)