1. Has "CTRL-Enter" been reassigned to do something else?
To check, go to Button (upper left hand corner) --> Word Options --> Proofing --> Customize --> Keyboard Shortcuts [Customize] button.
You want the "Insert Tab" option in the left hand column. Scroll down the right hand column until you find "Insert Page Break". Below the two columns, it will list what keyboard short cut corresponds to that action. It's possible that somewhere along the line that got reassigned to a different or disabled. You can reinstate it here.
2. Is this an upgrade to Word 07 or is this a fresh install?
Sometimes upgrades don't go smoothly, which would cause little glitches like this, and have to be redone. If this is an upgrade, you might try reinstalling Office 07 and see if that fixes the problems.
I'm not sure what the problem is with the find-and-replace, but that's what makes me think it might be an installation glitch since I've had that happen to me before, though not with 07 but with almost every other version of Word.
If worse comes to worse, check out the forums on Microsoft and see if it's a known problem. I've found the forums to be very helpful if I have the time to look through them.
Hope it shakes out for you.