Is your issue that you cant start database mail? Or that you think its started but are still receiving the message you posted?

If you cant start it then please can you post the output of sysmail_start_sp