In the current campaign, we have people who are able to quickly come up with characters and people who are rather slower.
Myself, I can put together a 1st level character in about 5 minutes, assuming I know the general type of character I am trying to make.
Player 1 is an Old D&D hand. He is also very creative. He whips together characters in anywhere from 5-20 minutes.
Player 2 is also an Old D&D hand, but he is terribly indecisive and looks not for what is optimal necessarily, but for what best represents his character. As such it can take him an hour or more to put a character together.
Player 3 is more of a White Wolf person, but he can put together a character in under 30 minutes -- again, the time is more due to taking the "right" mix of skills and feats, rather than necessarily the optimal ones.
Player 4 is an Old D&D hand, but is also something of a min-maxer. He takes about 40 minutes to put a character together, as he tries to metagame the character into submission.
Player 5 is new to rpg'ing. She comes up with fairly simple, straightforward characters, but double checks a lot to make sure she has gotten the rules right. She can take anywhere from 30 minutes to an hour, mainly out of hesitation.
Player 6 is another White Wolf person and sometimes gets huffy that she can't make the "right" character (e.g. "I could make the character I want if were were playing Werewolf!"). This tends to slow down the process quite a bit, as she is still "fighting the system". Character creation time, about 45 minutes.