Do it while you're on the lot.
I can't remember, but I think the change isn't immediate.
Use the story down button, go down a few stories, go back up, use the wall tool and then try adding another story. I think you have to let the game know that you can build more than 4.
That did the trick! I tried placing a wall and then the button showed that I could go up another level.
Thanks!