Die Suche hat lange gedauert, und hat sich über verworrene Umwege aber letztendlich doch gelohnt! Mein Problem konnte ich lösen.
Der Vergleich der phpinfo von einem System auf dem der Upload problemlos funktionierte mit meinem Server auf dem der HTTP Error kam, hat mich in die richtige Richtung gebracht.
Das Problem war offensichtlich, dass PHP auf meinem Server mit FastCGI läuft und in der fcgid.conf für MaxRequestLen ein zu niedriger bzw. gar kein Eintrag zu finden war.
Bei mir hat MaxRequestLen 134217728 (und natürlich anschließend Apache stoppen und neu starten) den Fehler beseitigt!
Vielleicht hilft es ja dem ein oder anderen weiter...