There are limits in how much you can delete at once. I avoid this problem
in the settings by allowing a Delete command that bypasses the rubbish bin.
It has one benefit and one drawback. The benefit is that there is no size
limit and it is much faster. The drawback is that it is permanent. I am not
sure why it worked as you described, though. To add the Delete command
which appears int he drop down menu go to Nautilus and Edit, Preferences,
Behavour tab and at the bottom will be a check box.