is it a brand new tank with brand new gravel? or has it been used recently? i've heard that the bacteria can lie dormant for a short period of time.
are there any plants in it? the bacteria can be found in plant roots and potting materials
is anything else in there from another tank (decorations etc)? you'd be surprized at what else you could find bacteria on.
in other words, no, its not normal, but that doesnt mean it's impossible. also, how big is the tank? if its just a small one you dont really need as much time for the bacteria to spread, because it doesnt have as much to cover. therefore, its more likely for a small tank to go through the cycling process faster than my 55 gallon for example.