Ah, so many posts to respond to...
H&S, the sample stats you posted are indeed too high for 1st level without tinkering with encounter levels etc. At 41-45 point-buy equivalent, they would be about as powerful as a 2nd level PC with 25 point-buy! (Based on existing ECL calculators, +1 ECL is equivalent to 10-20 extra points.) That means you would have to adjust all the encounters upwards by one level as well to challenge you players, but they still get XP based on their lower apparent level, etc...
If you really *want* your PCs to start out this buff (not just hero material, but closer to super-hero material), you should probably treat them as 2nd level to make sure everything balances out. OR you could just decide to start your campaign at 2nd level, and/or allow them to start with a +1 ECL race...
If you like randomness, but want to keep the balance that point-buy provides, here's some options for you:
1) Roll using your preferred dice method, then adjust stats up or down to match a desired point-buy value. If the point value of the rolled stats is too high, they are only allowed to adjust stats downward, and vice versa. This gives largely random stats, with a little bit of customization, and perfectly point-balanced.
2) Take a deck of cards and remove everything except for the 1-6 cards. Deal 6 stacks of 4 cards, remove the lowest card from each stack. Very elegant method (not mine, but I laways forget who came up with it), and it's a damn sight easier than rolling 24 dice! Equivalent to standard 4d6-drop-lowest, but tends to be much more balanced.
3) Aaron2 & Fenris's method: create a small table (I'd suggest 6 or 20) of stats you feel are balanced, then let them roll on that table (d6 or d20).
4) Roll only the first three stats using dice. The remaining three are equal to 25 minus the first three (max. 18). For each high stat you also get a low one, so the total sum of stats is balanced. For higher stats, subtract from 27, 29, etc.
5) Roll stats using your favorite method. Then calculate point value, and give PC with lower point value some extra skill points or starting XP to balance. I'd recommend 1 skill point or 50 XP per point-buy point below the highest point-buy value.