In Messages, go to the top of the list, press Menu and select Delete Prior. This will delete ALL unsaved messages, so if there are any you want to keep, make sure to save them before deleting.
Posted from my CrackBerry at wapforums.crackberry.com
Another way to delete many things at once is to select and hold # while scrolling then delete them. Not as effective for deleting everything, but helpful to get blocks at a time if you needed.