Apparently this bug is known and you're going to have to reload a previous save prior to beginning this quest. If you know Elder Scrolls games, then you know to save often and save alot. Saving is basically your one defense against glitches, issues, and quest or game-breaking bugs.
This comes straight from the Skyrim Wiki,
"A second bug on the Xbox can occur right when you exit Solitude and enter Skyrim. Gulum-Ei can sometimes not move at all and simply stand at the front gates. To fix this, you need to kill him and then reload the last auto save"
The page goes on to explain a few other bugs and gltiches that can occur, most of which are solved by referring to a previous save.
The Argonian you're tailing eventually ends up in the East Empire Company warehouse. He goes all the way around it to a business ledger, signs it, then back tracks a bit and slips into an almost hidden door into Brinewater Grotto. That is where you'll eventually catch up to him.
EDIT: Wow, apparently I'm going to have to check the dates on threads before researching and posting. To the member above me who raised this thread from the dead, it will be in your best interest to just create a whole new thread. This particular thread was made just days after the game was released. Do you have all the current patches?