I recently had a client who was trying to upload podcasts to her site and was having problems because the files were too large. I found this simple solution:
Add the Following to the php.ini File (If you don’t have a php.ini file, create one and add it to your wp-admin directory.)
memory_limit = 100M upload_max_filesize = 192M post_max_size = 100M file_uploads = On
http://www.wordimpressed.com/coding/how-to-increase-wordpress-file-upload-size-correctly/
The tutorial includes a screencast, which is nice.
*Extra note – For GoDaddy hosting, this file needs to be named php5.ini