As well as that place on Holburn St (Cafe Rosa?) there is the Gordon Cafe on King St. Great greasy spoon.
Good place in Torry as well IIRC but it has been years since I was last in there.
Had a similar experience in central Birmingham before. The only place open at 5am was a McDs - full of local buisness people having their breakfasts, including cafe-owners!
