This is similar to
SOLR-3377. That bug appears to have fixed this problem for 4.x.
I can see the effects of
SOLR-3377 when I test a query similar to below on the Solr 3.6 example, which is expected because SOLR-3377 was found in 3.6 but only fixed in 4.0. This bug is a little different, and exists in 3.5.0 for sure, possibly earlier. The first part of the parsed query looks right, but then something weird happens and it gets interpreted as a very strange phrase query.
query URL sent to solr 3.5.0 example:
Adding some spaces before and after cat:string1 fixes it: