After searching through the Internet, seems like this has happened with other Nokia phones, especially Symbian S60 ones, like X6, E75, E72. I tried changing the message tone to Nokia default, but didn't work. I also tried deleting all text messages in my Inbox, but also didn't work.
I have restarted my phone numerous times.
I was about to reset my phone settings (by using *#7780#) but I remember something...
I once had a similar problem with email message tone. The solution was to change my home screen theme to 'Active'. My home screen was already 'Active', so I switched it to another home screen theme and tada! My Nokia E5 text message tone works again!
So, the solution is:
1. Go to Control Panel > Settings > General > Personalisation > Standby mode > Home screen theme.
2. Choose another theme. You can go back to your favorite theme after making sure the message tone works again.
Good luck!
Note: this bug dates back to around 2003 or probably earlier. Ironic that it still occurs with a modern 2010 device.
