However, we were still not able to upload large files.
I called Microsoft and they confirmed that the the steps listed in the link above should be all we need, but there are cases where another minor change in the site's web.config file is necessary. Go to your site in IIS and explore to it (right click -> explore in IIS 7.0). Find the web.config file and make these changes at the bottom. Sorry for the image but blogger.com doesn't like these characters and I'm not going to escape them all out!
I did not have to reboot the server or even cycle IIS, it worked the next time I tried to upload a file. Apparently Sharepoint was configured correctly but IIS still would not recognize the new settings so we had to change it manually.