File upload error "Files must be less than x MB" despite file being smaller than x
The upload_max_filesize parameter in php.ini (or accessed elsewhere) must follow the file size naming that PHP understands:

upload_max_filesize = 100MB  // NO
upload_max_filesize = 100 MB // NO
upload_max_filesize = 100 M  // NO
upload_max_filesize = 100M   // YES


Also keep in mind that many shared hosts will cap this value at a higher level.  So ask your host and use something reasonable like 25M or 50M - just putting in a ridiculously high value like 500M won't necessarily help you.