Ok, the problem is that the option box is built with the same code that the upload option box is built by. The code that builds this option box looks at what type of upload you are doing (for sale, wanted...) then only shows the cats with that type in the drop down. The problem is that when you search you want all the categories displayed. Here is a quick fix to get you by for now.
In pp-inc.php look for
Code:
Content visible to verified customers only.
After it put
Code:
Content visible to verified customers only.
This will tell the page that you are searching and not to add the $temptype value to the query when building the drop down box.