Did you get this working? I'm having exactly the same problem. Followed the instructions here http://doc.silverstripe.org/leftandmain and all works fine if I put my custom templates in the cms->templates folder but if I put it in my site templates folder I get:
[User Warning] None of these templates can be found in theme '': VimeoAdmin_left.ss, LeftAndMain_left.ss
I already tried that - I copied the LeftAndMain.ss file to the mysite/templates/Includes from the CMS/templates folder and even created an empty VimeoAdmin_left.ss file in mysite/templates/Includes (I don't actually include that in my VimeoAdmin.ss file though) but I always get an error unless I put VimeoAdmin.ss in the CMS/templates folder.
This reply might be too late to help, but standard practice for overriding module themes is to place them in a folder called /themes/yourtheme_modulename. As the CMS is just a module I'd suggest /themes/yourtheme_cms
Sorry, I've just tried it now - turns out I was wrong in this case: there is no 'theme' selected when you're in the backend. To get it to work, you put it in /mysite/templates/Includes/ClassName_left.ss (and ClassName_right.ss)