After checking the joomla forums and putting some pieces together, i finally got this same problem resolved. First and foremost, your hosting company (all) will probably not know what you are talking about.
2. Find out exactly where your php.ini file is. To do this, open your Joomla admin > Help > System Info > PHP Information.
3. Look for 'Loaded Configuration File' - This gives you the exact path/location of your php.ini file.
4. Edit your .ini file and add these lines:
upload_max_filesize = 100M
post_max_size = 150M
max_execution_time = 500
max_input_time = 500
Your 'limits' may not have to be that high, but heck, after spending so many hours trying to find the solution, i didn't want to take any chances.
That's it! Worked for me! Hope it helps.