As previously mentioned the addition of the .htaccess code can fix this issue. However, some Hosts do not like php settings in the .htaccess for those hosts (1and1.com is one such Host) you need to create a php.ini file inside the wordpress install root. Simply add the following code:
memory_limit = 32M ; Maximum amount of memory a script may consume (32MB)
upload_max_filesize = 10M
post_max_size = 10M
Make sure that upload_max_filesize and post_max_size are large enough to accommodate the files to be uploaded. It should be noted that memory_limit may need tweaking as well.
