Plugin update failing; "could not remove the old plugin"

When attempting to upgrade a plugin via the Update interface, the following response is returned:

Downloading update from http://downloads.wordpress.org/plugin/%5BPLUGIN PACKAGE].zip…
Unpacking the update…
Installing the latest version…
Deactivating the plugin…
Removing the old version of the plugin…
Could not remove the old plugin.
Plugin upgrade failed.

Checking the file system afterwards reveals that the individual plugin directory (in this case [WORDPRESS DIRECTORY]/wp-content/plugins/[PLUGIN DIRECTORY]/) is empty, but still exists. At this point, I’ve tried two solutions:

– Changing permissions on the /wp-content/plugins directory to 777, just to eliminate that as a possibility; had no effect, and was insecure to boot, so permissions were restored
– Defining ‘FS_METHOD’ in wp-config.php as ‘ftpsockets’ and providing all the FTP connection info; the hosting environment can’t seem to connect to itself via FTP, so this one failed.

The hosting company insists that everything is configured properly from their end. I’m using the same kind of setup on WordPress that I’ve used in other environments, so there’s nothing unusual there. WordPress doesn’t seem to have an issue with deleting the files inside the plugin’s directory, so why it would indicate that it would have issues removing the old plugin is beyond me.

WordPress version 3.0.4, running on PHP 5.2.13