I've found the solution
I removed "/usr/lib/cgi-bin" from the Document Root. It is now blank, and the server will serve my php page!
I didn't see that mentioned in the Howto, but perhaps it is something that was supposed to be properly set by the wizard. With the version of Cherokee I am using (1.0.8) there was not wizard for setting the Behavior rules.