I would question what you are wearing on your arms and legs as well?

I wear booties in the high teens and don't experience anything colder than 15F really. I have heard good things about northwave,lake and specialized winter shoes. If you get winter shoes I think you will be fine with anyone of them as they all get pretty good reviews. Make sure they are big enough for some wool socks