I built myself a decent sized house with a basement and it said it wasn't valid housing. So I built another one that is a very simple room with walls (dirt walls on the background, wood "walls") a door, two doors, a table, a chair, floors and light sources. I've gone over and over it and made sure there are dirt walls everywhere. It still says it's invalid housing.
I'm playing on Xbox 360.