Drupal 6.22 - Colorbox plugin missing
Revised:

Your directory structure is correct.  Your file directory permissions are not.  Your chmod a+w command gives read and write permissions.  In your case, to get rid error message you must have read and execute permission on the /sites/all/libraries/colorbox &amp; /sites/all/libraries/colorbox/colorbox directories and read permissions on the 2 javascript files.   Colorbox.module does a file_exist call 

if (file_exists($library_path .'/colorbox/jquery.colorbox.js') &amp;&amp; file_exists($library_path .'/colorbox/jquery.colorbox-min.js')) {

Depending on your operating system, and setting, PHP's file_exists() function is handle differently.