Many props to Phil Scott over at weblogs.asp.net. His post entitled "404 Errors with FileUpload with IIS7" just saved me many hours of headache. While the issue was exactly the same, I've entitled this post a little differently as for me it was not immediately apparent that IIS was the culprit.
The meat of the issue was 404 errors received while trying to upload a file. This worked perfectly in the development environment (my laptop), but failed almost all the time on the server.
The real culprit was IIS7 and the web.config. Here is the page on the IIS website concerning the system.Webserver/requestLimits section.
Here is the section that ultimately fixed my issue: