Can't upload theme - File upload size issue?

I am trying to upload a third party theme, via Themes > New > Upload.

I select the required zip file which uploads to 100% but then fails to an error page that only says 'Are you sure you want do that?'.

When I logged it with the theme vendor they said it is the file size upload limit, however I've changed that to 5000m and it still won't work (it only needs 15).

I can ftp it but I'd like to understand why this isn't working, it's a real pain.

Thanks, Neil.