I would suspect that James is on the right track here, although there could be two problems you're encountering.
Either a memory issue on the server, in which case increasing WP's memory in the wp_config.php file:
As well as an .htaccess file fix of:
php_value memory_limit 64M
and finally the php.ini update:
memory_limit = 64M ;
Do keep in mind that some servers require the .htaccess and php.ini changes to be located in the wp-admin folder, not the root. I've seen situations where it even needed to be placed in the wp-includes directory and wp-content to work properly for uploaded.
The second issue I've encountered on some hosting environments which causes an issue similar to this is permissions. If the above doesn't work, try changing all the files and all sub directories to 777, see if that helps. Obviously you don't want to keep it at this level but as a test it will help clarify if it's the server's permission settings.
Finally, it may simply be the server. Run phpinfo() to ensure that your server is running everything it needs. I have 3.0.1 installed in around 30 server configurations across a variety of hardware and software, there are hiccups on some but not on most.
Hope that helps.