First and most important step. Check and make sure your hosting account has the available space. Login to your hosting control panel and check how much disk space you have used.
Next verify your PHP settings are actually what you have tried to set them to (this will tell you the limits set in PHP):
Create a PHP file in your root WordPress directory:
Inside that PHP file put:
Then browse to
You can review the PHP settings to verify the overrides you are using are actually being used. After doing this, remove that file.
Review this site for more details on checking and setting upload limits in WordPress:
Next check your folder permissions, using FTP or your web hosting control panel, make sure that directories are set to 755:
Have you tried uploading files via FTP to verify that you can actually upload to your hosting account?