I assume that they began work on the second death star while the first was still being constructed. Why would you build just one massive super weapon when you could build two? Or three? Or...you get it. So, even though there is no mention of it, I would assume that in the middle of building the first one, they chose another secret location to begin building another.

Bothan spies aren't the best source of information...the Empire could have easily been working on that thing a lot longer than the plans showed.

That's my explanation anyway. It hasn't really bothered me since I came up with that.