Even if you have an external memory card, it is possible that all your applications, pictures, videos and music are on the internal memory card of the device. You can try going to Settings -> Applications -> Manage applications and tap on the All Applications tab. You will see a list of all applications that are installed on your device. To clear your internal memory, try to move some of them to the external memory card. To do that, you can tap on any application from the list an select Move to SD card.
If this isn't your case (you have plenty of space on the internal memory and the error still pops up), you can try to reboot your phone and try again.
