I know almost nothing about Preview, but I was having the same problem, and after an hour of struggle I solved it. Here's what I did:
1. In the toolbar, click the "Edit" button (the one with the little pencil). This opens the "Edit Toolbar."
2. Click on the rectangle with the dotted lines on the *right* side of the edit toolbar (it says 'rectangular selection' when you hover over it). [The mistake I had been making was clicking on the solid rectangle on the *left* side of the toolbar (it says 'rectangle' when you hover over it). I don't know what that's for, but it won't let you crop.]
3. The cursor will turn into a "+." Use this to make your selection.
4. Choose "crop" from the Tools menu.