Are you on shared hosting by any chance? Shared hosts tend to limit the max uploadable file size on their end and there is nothing you can add to your scripts to change that. If not, then I am mistaken and this is not the solution you are looking for.
However, if you are on shared hosting it might pay to contact them and ask them the max allowed file sizes they allow their shared hosting accounts to have. Some hosts however let you create a php.ini file, drop it into your site root directory set some hosting variables like upload limits, etc.
Try creating a file called 'php.ini' without the quotes and put in the following:
upload_max_filesize = 64M
post_max_size = 64M
Then place the php.ini file you just created into your Wordpress root directory.
A good way to see if it is your host or Wordpress installation is to create a simple file uploading test and then try uploading the same file. If you have the same issue, it isn't Wordpress and is your server configuration.
Create a page called "file.php" and then add in the following code:
<form enctype="multipart/form-data" action="upload.php" method="POST">
<input type="hidden" name="MAX_FILE_SIZE" value="512000" />
Send this file: <input name="userfile" type="file" />
<input type="submit" value="Send File" />
</form>
Now create a file called "upload.php" and add in the following:
<?php
$uploaddir = 'uploads';
$uploadfile = $uploaddir . basename($_FILES['userfile']['name']);
echo "<p>";
if (move_uploaded_file($_FILES['userfile']['tmp_name'], $uploadfile)) {
echo "File is valid, and was successfully uploaded.\n";
} else {
echo "Upload failed";
}
echo "</p>";
echo '<pre>';
echo 'Here is some more debugging info:';
print_r($_FILES);
print "</pre>";
?>
Example code taken from here: http://snippets.dzone.com/posts/show/3729
Now see if that lets you upload a large file. If not, then we'll further try and debug your Wordpress installation to try and rectify the issue.