Do Not Ban
Ok, Nidoqueen is definitely the more controversial of the two suspects, but in my mind it's not broken. Nidoqueen is a giant threat to stall, as it resists Stealth Rock and is immune to Toxic Spikes, doesn't take Life Orb recoil, and is immune to paralysis and burn. This makes it very hard to beat if you're using a defensively based team, as residual damage is the major way damage gets dealt by those kinds of teams. However, while Nidoqueen is powerful, and Nidoqueen is bulky, it's not bulky enough and it's not powerful enough. It doesn't OHKO the bulkier special walls that are common on defensive teams such as Slowking and Cryogonal, and it is 2HKOed by most STAB moves on stall teams. Poliwrath, Steelix, Earthquake Tangrowth, Slowking, Cryogonal, and Lanturn all make it very difficult for Nidoqueen to switch in. Stall teams can generally play around it reasonably easily, especially since it just uses Sludge Wave into a coverage move most of the time.
Nidoqueen is pretty similar to Magmortar, in that it is extremely threatening to stall, has very few counters, but isn't so great against offense. Of course, the key difference is that Nidoqueen isn't hurt nearly as much by hazards, and is immune to the two most common status moves. One of the major points brought up by those who wish to ban Nidoqueen is that it hurts stall too much to be healthy for the metagame. How is Magmortar any different? Is Magmortar broken? Of course not. Is Nidoqueen broken? No.
Offense also deals with Nidoqueen reasonably effectively as well, with several bulkier Pokemon being good checks to it. Uxie is one of the most common leads for offensive teams, and it happens to be arguably the best counter to Nidoqueen in the metagame. Golurk is also a wonderful check that 4x resists Sludge Wave, and can take the Earth Power that follows while KOing with Earthquake. Gallade is a bulky attacker that can deal heavy damage with Zen Headbutt, and Feraligatr can do the same. You can also use good lure sets to beat Nidoqueen; Life Orb Rotom-C can lure in Nidoqueen that thinks it will use Volt Switch, and when no Leftovers show, Nidoqueen is obliterated by Leaf Storm. It's not a foreign concept in a healthy metagame to have Pokemon that have almost no viable counters, such as Salamence, Terrakion, Kingdra, Magmortar, and others. Nidoqueen is just another one of them.
While Nidoqueen has definitely impacted the metagame, and burst onto the scene as a top-tier threat, it's still not broken. In a way, Nidoqueen is similar to Moltres; difficult to counter, easy to check. It's even more influential than Moltres, but this is a different metagame, and new metagames require adaptation, not banning.