I am in the process of trying to convert the ezmlm module to the new forms API. I am doing this so I can learn the forms API. I am one of the maintainers of the ezmlm module and it is a very, very simple module.
Once I learn the forms API fairly well, I will be happy to help other people with their conversion efforts, write more documentation on the API and/or convert more modules. I just need to get it all clear in my head first.
However, I'm having some problems converting a simple form in my module. I spent several hours reading all the latest documentation and working on it last night, and I've run into a few things where I am not clear on how it should work.
I was in the same situation as you, and I've found that when in doubt, it is best to open up form.inc and look for theme_<#type>, e.g. "theme_checkbox", "theme_select". Then you can see what HTML is output. If you still can't figure it out, remember (or look for) a core form that is similar to the one you have, and see how it is made ;). By the way, about your checkboxes... #tree is indeed a way to get arrays, but remember that if possible, you should use the plural checkboxes and radios types. Steven