The Gmail team team released an improvement over the size of attachments which we can send over Gmail. Now the size is 25MB, previously 20MB.
However, please note that you cannot upload an attachment of more than 10MB on the flash (default) uploader. You need to switch to the classic (tedious if you have to send multiple file) uploader to be able to take advantage of the 25MB attachment option.
You might also need know that if the destination address of the attachment does not support attachments of 25MB, then it will fail to deliver.