What happened?
Sounds like the database became corrupted for some reason. Perhaps it's been corrupted for a while and it just recently got really bad.
How can I fix it?
In opera:config, under the "Mail" section, set "Mail Database Consistency Check Time" to 0, save and shut down Opera. When Opera asks, run a database check. Opera will then shut down, scan the database and try to fix some things if it can. The results will be logged to recovery.log in "/home/user/.opera/mail".
If that doesn't fix it (and it likely won't), rename the mail folder while Opera is closed. Then, start Opera up and set up your mail accounts again. Then, goto "Menu -> settings -> import and export -> import mail -> import generic mbox -> add folder" and browser to "/home/user/.opera/mail/store/accountN" where N is the number for the account as seen in accounts.ini. In the import dialog, choose what account pop account to import into. Repeat the steps for each of your POP accounts.
After the importing is all done, if you have duplicates of messages (an imported copy and a copy fetched from the server when you set up the pop account), delete the imported copies.
You'll have to readd your labels etc., but it'll get your messages back.
There's no way to restores you feed messages (as feed messages. You can import them as mail messages though) that way. But, you can export your feed list before you close down Opera and rename the mail folder and import it into the new mail folder. You'll have to readjust each feed's update interval though.
Now, if the messages in question were removed from the server and from the accountN folder, then they're gone.
Also note that for IMAP accounts, you just set them up again. You don't import at all to restore them.
On another note, if Opera just isn't seeing new messages on the server anymore, you can have Opera redownload all messages in the inbox for the pop account (and fix the problem at the same time) by deleting the uidl file for the account in the pop3 folder in the mail folder.
Also, if you have the exact same setup on windows, you can just copy the mail folder and contacts.adr and use them to replace the ones on Ubuntu. Then, it'll be an instant fix.