For a new system, I think its important to run through a long campaign just using the rules as written. Once everyone has a handle on it, then you can start introducing house rules. Every edition of D&D has required the DM to rebalanced encounters - though I usually just choose weaker or stronger enemies, rather then nerfing or buffing their base statistics. Perhaps that would be a better solution - once everyone has played for some time, ignore CR (or whatever they're calling it now) and use your own best judgment.

But seriously, give everyone a chance to get used to the rules. It may be that your players have all just made weak choices, not that the monsters are too strong.