Verify if you are exceeding the maximum size specified under Maximum upload size in the Web Application General Settings page under SharePoint Web Application Management. For detailed steps on viewing the max size & changing it, check this MS KB article - http://support.microsoft.com/kb/925083
By default, SharePoint allows a maximum file size of 50MB that can be uploaded into any document library.
You can specify a maximum file size up to 2,047 megabytes.