Carbonation time really depends on a variety of factors:
The kind of yeast you are working with, how much of it is suspended in the beer that goes into the bottle, the temperature that it sits at while carbonating, and of course what is there to consume for sugar.
Looking over my own records, I can see that beers that age longer before bottling tend to take longer to carbonate, when I'm using the same yeast, because more of the yeast is settling out during that aging period.
Cooler temperatures make a HUGE difference. I had one beer that still wasn't fully carbonated after over 2 months (actually almost 3) in my basement, where the temperature was in the low to mid 60s. I figured I must have screwed up the amount of my priming sugar or something, but then I put them in a room with an electric heater and set it at 75, left it there for 2 weeks, and I haven't had an un-carbonated bottle of it since.
Last, when you are bottling, you are putting the priming sugar mix into the bucket before siphoning in the beer, right?