Jeff,
Also, what does it say under: Admin > General Settings > Directories & URLs > Show server upload limits (this is a link on the right)
There's a number of places where web hosts limit max upload sizes, it might worth sending your hosting support a quick email to ask them how they recommend you update it. Sometimes it's the php.ini, sometimes it's in .htaccess, and sometimes they lock it down so you can't change it without asking them.
Let me know what you find out. Thanks!
Dave Edis - Senior Developer
interactivetools.com