Overcentralization
The argument here (most often used with regard to Kyogre and Groudon, the weather ubers) is that if we allow a Pokemon, there will be less usable Pokemon. "If you allow Kyogre, no one will use Luvdisc, Suicune, Milotic, Butterfree, Pikachu, or Geodude, and all teams will be forced to carry their own Kyogre and a Ludicolo, so there will be less usable Pokemon." This argument is entirely statistical. That means that if this is the reason for uberizing a Pokemon, we can use the Shoddy usage list to verify whether this argument holds water. This is the most objective of all the definitions of uber.
No counters
This is the main reason for the complaints behind Wobbuffet and, for different reasons, Deoxys-S. I'll start with Wobbuffet, because it's easier to discuss with regards to the "no counters" situation.
Wobbuffet's ability, Shadow Tag, means nothing can switch out of it. A counter by definition must be able to switch in. Unless the Pokemon out is holding a Shed Shell, has Baton Pass or U-turn, or has Role Play, Skill Swap, or is also Wobbuffet (or Wynaut), you cannot bring a counter in on Wobbuffet. Proponents of this argument must address the issue of Dugtrio, Trapinch, Magneton, Magnezone, and Probopass.
For other Pokemon, the "no counters" argument takes a slightly more vague reasoning. Imagine a Pokemon with 500 base Attack, Special Attack, and Speed. This Pokemon could OHKO anything it faces (and is faster than everything), so the only way to stop it would be with priority moves like Quick Attack, Extremespeed, and Sucker Punch (or an opposing version of itself that is faster). However, unless there were a similarly defensive Pokemon, you couldn't bring in any of these Pokemon to stop it, and thus you'd be forced to sacrifice something to bring in your "counter", and it would likely switch out and come in later to repeat the cycle. Here, the problem isn't that you cannot switch in at all, but that you cannot switch in safely. Obviously this is more extreme than any real example, but Pokemon like Deoxys-A and Mewtwo are similar to this scenario.
Alternately, consider the case of a Pokemon with base 500 HP, Defense, and Special Defense. Here, you can switch in safely (assuming it has low-average offenses), but once you're in, you can't do anything. A counter must be able to switch in safely and threaten the Pokemon it is said to be countering. I may be able to switch in Milotic safely on a Substitute, Calm Mind, Surf, Ice Beam Kyogre, but what am I going to do as it Calm Minds up?
Luck
One of the arguments surrounding Garchomp is that Sand Veil means that even if you have a counter for it, you may not be able to stop it thanks to Sand Veil missing. The more luck influences Pokemon, the less skill does.
Hyper-offensive Pokemon like Deoxys-A also have an element of luck. You are forced to make guesses as to what move it will use and what set it has as soon as it comes out. This decision is forced before you can possibly have enough information to stop "guessing" and begin "predicting".
This is one of the major arguments in favor of banning Double Team / Minimize and OHKOs.
This is probably the most subjective reason of all, as you have to make a judgment on how much luck is too much (or whether the increased element is even there to begin with).
