First of all, i'd enable debug output (at least in the admin site) and have a close look there.
As a shot in the dark: Check PHP and Apache's max file upload sizes, check unix/linux filesystem rights and finally check your Apache Rewrite rules. But from you post, i'd guess the upload size exceeds some limit.