Is my webhost the reason I can't upload attachments with standard modules?

When I found I could not upload attachments I disabled modules, shifted to Garland and found I still cannot upload files.
Having stripped back to the basics, and still not being able to upload, I am now thinking it is the server.
Have I missed anything? Is it the server? And if the server what do I need to ask the help desk?

This site is on a web host I have not used before (client's choice). They say they have other people using Drupal on their server, but they do not know about Drupal.

Using standard page with attachments enabled. Progress bar does its thing, but nothing uploaded, and no attachment showing on the page.
Currently I have only Admin menu, Module Info, Admin role, Database logging and Upload enabled. Garland theme.
This is Drupal 6.13. I updated Drupal and all its modules to see if that would fix the problem.

======
More info:

The server is Apache, PHP 5.2.6, MySQL 4.1.22, Memory limit 128mb

I have set file permissions on the server to 777 for sites, default, every directory within default. The web root folder is 755.

I have File uploads enabled.
File system path: sites/default/files
Temporary directory /tmp
Public download method
I have upload set (for me) 500mb total limit, 2mb per file, extensions: jpg jpeg gif png txt doc xls pdf ppt pps odt ods odp rtf
The size of the files I have to upload: 12kb, 60kb, 240kb.

I have tried different kinds of files, and it correctly refuses files with the wrong extension, but does not explicitly refuse the wrong file size (2.6mb, with a 2mb max) (although it does not work).

When I was trying to use Filefield to upload (before stripping back to basics) the error message was "The file in was unable to be uploaded" which apparently is Drupal error text not Filefield or imagefield.
The logged error message is: { "data": "\x3cdiv class=\"messages status\"\x3e\n\x3ca href=\"/admin/settings/site-maintenance\"\x3eOperating in off-line mode.\x3c/a\x3e\x3c/div\x3e\n\x3cdiv class=\"messages error\"\x3e\nAn unrecoverable error occurred. The uploaded file likely exceeded the maximum file size (2 MB) that this server supports.\x3c/div\x3e\n" }