Update: This has been fixed with AutoBlogged v.2.7.3 and later.

[Developer's note: For other plugin developers looking for the solution, you need to make sure there are no files in the root directory of the zip file!]

Issue
This error is caused when you use the WordPress upload feature to install a plugin from the Add New plugin page. Unfortunately, this feature cannot handle a zip file that contains folders so it places the files in a subdirectory where WordPress cannot see the plugin header files to activate the plugin.

For example, the autoblogged.php file would be installed in a directory like this:
/wp-content/plugins/2.xx/autoblogged/autoblogged.php

Background
Since WordPress v2.8, there has been a feature to upload and install new plugins directly through the WordPress admin back-end by browsing for them on your local hard drive. WordPress will upload the zip file, extract it to the /plugins directory, and then try to activate the plugin. The problem is that since the AutoBlogged zip file contains the plugin files in a subdirectory, WordPress will create one directory with the name of the zip file and then the /autoblogged directory under that. Since that places the plugin file two directories deep, WordPress cannot find it and reports an invalid header. This same problem occurs with any plugin that uses subdirectories in the zip file, and there are many that do.

Solution
To correctly install AutoBlogged, you should use FTP or your hosting control panel’s file manager to upload the autoblogged directory directly under the wp-content/plugins directory. In other words, the full path to autoblogged.php should be:
/wp-content/plugins/autoblogged/autoblogged.php

If you have already used the WordPress upload feature to upload the plugin, you can fix it by moving the /autoblogged directory directly under the /wp-content/plugins directory.

Comments
Obviously, we could fix this ourselves by placing all the files in the zip file without any subfolders, which we tried for a short time, but then found that many users were confused about where to put the files when uploading them via ftp. By zipping them into the autoblogged directory it is pretty intuitive to upload that entire /autoblogged directory to the plugins directory in WordPress. Another benefit is that it allows us to place other files in our zip file that don’t need to be uploaded to your server.

We personally consider this to be a WordPress issue. One solution would be for them to recognize that zip files might actually contain subdirectories and unzip the files accordingly. Another solution would be to allow WordPress to activate plugins that are one or more directories deep under the /plugins directory. And of course, they really should fix their error message saying that our plugin header is invalid when in fact they just can’t find the file that they uploaded to the wrong place.

See Also:

http://wordpress.org/support/topic/280262

http://ijstyles.com/wordpress-2-8-issues-how-to-solve-plugin-does-not-have-a-valid-header/

http://wordpress.org/search/%22The+plugin+does+not+have+a+valid+header%22?forums=1