Article Number: KB-04470 on Blackberry.com addresses this issue. It worked for me today.

Problem
On the BlackBerry device, you select a message, click the trackwheel, and click Delete. The message is not deleted from the device.

Cause
The message list index is corrupt. As a result, the operating system of the device cannot reference the message ID and delete the message from the list.

Resolution
Back up the device and clear the device message database.

Warning: Clearing the device message database results in loss of messages on the device. Make sure to create a backup first.

Create a backup:

Connect the device to your personal computer.
Open BlackBerry Desktop Manager and select Backup and Restore.
Click the Backup button. Save your backup file in a folder that you can access later.
Click Save. The backup process completes.
Clear the device message database:

From the Backup and Restore window, select Advanced.
From the Handheld Databases list, highlight the Messages database and click Clear.
Click OK when prompted with a warning message. The device message database is erased from the device.