Bell Curve Rolls will add some predictability to the game and favor player choices over random rolls. I would just use the tables from the variant to determine any changes, and I would suggest just rolling 3d6 twice for Advantage/Disadvantage to keep the mechanic the same, although as SevenSidedDie points out, the probabilities are similar. Ace in the Hole's equivalent would be 16-18, though since it's a 20th level ability and 18 equates to "automatic success" in the Bell Curve Rolls, 18 is probably appropriate. Otherwise, I think your changes make sense. In the end, equally applied to NPC and PC alike should go a long way in making this variant work.
Honestly, I'm not truly convinced that there is a problem. As you say, the 'problem' only appears as a significant setback with extreme tradeoffs. A character at PL10 who is at 16 attack/4 damage is not someone who is supposed to be going toe-to-toe with equivalent PL opponents.
People who are attack shifted should have a thematic reason for the shift. This theme should also indicate how they can rectify the situation.
Batman, for instance, is attack-shifted. He compensates by having a versatile selection of attacks with varied defenses. He also uses things like Set-up and Teamwork to benefit other heroes (such as those unfortunate bricks who are heavily damage-shifted but can't land a blow on an agile opponent).
That said, the suggestions you give for 'fixing' this don't seem to be good fixes for me. Both are variations of having your cake and eating it too by letting accurate attacks deal more damage. Autofire, for instance, means that putting 2 points into your attack is strictly better than putting 2 points into your damage: you are both 10% more likely to hit AND your attacks do 5% more damage.
Mutants & Masterminds is a comic book-inspired Super Hero game. Not all characters are supposed to be able to do everything. If you are being presented with a foe that your typical attacks can't hurt, consider what your favorite super hero does in his/her comic when confronted with that situation. Spider-man doesn't complain that it isn't fair his punches can't hurt Rhino, he uses his combat advantages to make him charge a power transformer or get stuck in a wall and webs him in place.
You don't need a mechanical 'fix' for a 'problem' that is intentionally built into the system. If you don't want to be faced with a situation where your character can't damage his foe, don't play a significantly attack-shifted character.
You can mathematically analyze mechanics to your hearts content, but if you are doing that at the expense of a fun game, you're missing the point.
Addendum: One thing that attack-shifted people have going for them is MultiAttack. I was reminded of this by this question. Multiattack adds +1pp/rank to the cost of an Effect, and allows you to do additional damage to a single target if you exceed their defense (+2 or +5, depending on how much you beat them by). You still have to be able to damage them with the attack (so you have to beat their Impervious threshold) to do so, but it addresses the tradeoff issue in much the same way as Autofire does. It also gives you a few other combat options (hitting multiple people for a minor attack penalty or giving an ally a Defense bonus).
Edit: In response to this being called a 'poor answer that dismisses the question', allow me to elaborate on my reasoning for being 'dismissive':
Attack is already cheaper to buy than Damage. Yes, if you just pump up your Str, you get melee attack and damage. But there's easier ways to buy your attack up. Most simply, you can get +2 attack / 1 pp by buying your attack as a skill (Close Combat: Unarmed) with a narrow focus. So an attack-shifted person who meets his caps can (and typically does) have more pp left over to buy things with.
The question points out that critical hits, which always hit, are a huge problem for attack shifted people: 1/20 hits, the defender will always lose anyway. The question indicates that this will be an auto-hit with +5 damage 1/20 times. Unfortunately, that's not right. This isn't always the case: critical hit must still exceed the targets Defense to get the +5 damage (or Alternate Effect). Of course, for a heavily damage-shifted character, one attack landing might be all they need.
The 'math' that is shown is overly simplified and the graphs are inconclusive. The graphs simply show numbers from -5 to +5, but don't indicate which direction the shifts go. They also assume two characters are simply standing and punching each other every round. Does this seem like something reasonable in a game?
The question, in my opinion, completely fails to demonstrate a real problem with the system. By narrowing it down to pure trade-offs and ignoring things like the fact that players typically have other party members assisting, the multitude of attack-boosting skills a teammate can have, and the many types of Effects that can render a character combat-ineffective without resorting to Damage, the question artificially narrows the system down to a single mechanic. The mechanic in question does have a bias, but the question neglects the many corrections for this bias which exist in the game.
The question seems to completely ignore any Effect other than damage. When simply hitting your target is enough (such as with a Chi attack resisted by Will - built as an Affliction with whatever penalties you like) being attack-shifted is purely better than being damage shifted.
Ultimately, the answer to this question is simple: work with your teammates to overcome your weakness. Watch an episode of Justice League where Batman and Superman work together. Watch Young Justice, and see what Robin does while Superboy is pummeling things. Watch Teen Titans and see why a young Nightwing is considered good enough to be on (and hell, LEAD) a team with a master of magic, a cyborg that can crush mountains, and an alien who can melt tanks from across the room.
When evaluating any system, you can't simply look at a single mechanic (in this case, trade-offs) - you have to consider the whole game.
Best Answer
My group uses the GameMastery Critical Fumble deck. We don't use it on every natural 1, but we use it on 1's when there's something else going on (in an area that's Unhallowed, for example, or in a cursed place or wild magic place or plane of the Abyss) to add to the atmosphere of threat besides a random roll penalty. It is also available as iFumble as an iPhone app. There are Melee, Ranged, Natural, and Magic options (so 1's on spellcasting rolls can have magical side effects as well).
Randomly drawn examples:
There's 52 cards with all 4 types on each so it doesn't repeat too often. The conditions are unfortunate but not instant death or decapitation type stuff, usually inflicting short term conditions (flat-footed, confused, dazed, etc.). Usually for 1 or a small die of rounds. Pulling some cards... -2 to AC for 1d4 rounds, sickened for 1d6 rounds, confused for 1 round... So this might be a better fumble-selection method than the current table. I do recommend trying to get him to lighten up on fumbles all the time, try to sell him on the idea of "it should happen when, you know, we're in an evil shrine or plane or someone's put a curse on the group or something, that would make it cooler."