A while back we wrote about backing up a Gmail account using Thunderbird. That doesn't work for restoring but you could at least have access to all your old emails.

But I've recently discovered a small application that allows you to both backup and restore your Gmail emails in Linux with just a few clicks. The application is called "Backup Gmail" and you can use it to backup Gmail either from the command line or using a graphical user interface. It uses IMAP, meaning that restoring your emails will also restore their labels!