I also DM a campaign where I allowed the players to roll, but my experience is not similar to Iron Sky's.
I have 5 players. 3 rolled pretty well (above point buy), with one of those being really quite good (I think he had 3 17s, a 15, and then some lower teened stats). 2 rolled poorly, and I let them use point buy instead.
My findings are that it hasn't made much difference. Certainly, by allowing the unlucky to use point buy, there is no feel of unballance as between the various players. Indeed, the only character with an 18 pre-racial in a stat is one of the point buy characters. Indeed, its fairly unlikely for a rolled character to have an 18, so in the builds that favour an 18 pre-racial in a stat, point buy will actually have a better prime stat.
So, rolling DOESN'T give one an advantage as to their prime stat - so, rolling/point buy characters will have similar to hits and damage will be appropriate for their class and role. It likely does give a boost to their secondary and certainly their tertiary - this makes effects and boosts triggered off of those stats more powerful. It likely gives characters a bit higher con (and a few more HPs). It increases skills and NADs that aren't based on the prime stat. The big effect is that it makes it much easier to meet feats with attribute requirements, therefore opening up options that a character would not have otherwise had.
Some of these changes I like - for example, I like that it narrows the gap between the high skills and the low skills in the party, making more skills viable for skill challenges and helping reduce it being the same guy who always uses diplomacy, for example.
I too find that n or n+1 encounters are easy, n+2 or n+3 are average and only n+4 or above are difficult. That said, I don't think that's because of allowing rolled stats. Rather, other factors such as player tactics, not being a "balls to the wall" GM who uses the best tactical options for his monsters, lots of party healing and generally short adventuring days play a bigger role.
My experience as a PC matches this - I had a warlock with rolled stats. When PH2 came out, the DM let me remake the character as a sorceror, as that better matched the character concept. When I did so, I also got the DM's permission to ditch my rolled stats and use point buy instead - the rolled stats were on average better, but using point buy let me get better stats in the attributes that actually mattered to me.
That said, my players are not optimisers, and have not hit paragon yet, so your mileage may vary.
My own opinion is that you should simply tailor your encounters to the level that is fun for your party, point by or not point. Then, tailor the experience to match the pace of progression that's good for your players and the campaign. Myself, I simply use more challenging encounters (I like having a lot of monsters on the board - makes the party wizard feel useful), and give normal XP for them. I don't give out quest XP, however.