Cannot upload images larger than 2MB
 

Filetypes are set to 5 MB max size
Categories are all set to 5 MB max size as well...

any user attempts to upload a file over 2 MB and it fails with

Invalid File

Any ideas?

This is usually a server PHP configuration restriction this is above any software settings. This is set in your servers PHP configuration usually in php.ini found on the upload_max_filesize line and is by default 2mb in most any php install.

What chuck wrote is correct in 99.99% of cases.
for the 00.01% remaining and IF you are using flash uploader make sure ALL filetypes are set to 5MB, even the ones you are not using.
(this is only needed if you are using flash uploader)
Luc