I used to think very much that Regulus was broken, but I overcame that line of thinking by playing him a great deal, and seeing what beat me. After playing my absolute jerkiest--walls of mines, harassing from out of range, attacking towers in my spare time--I got repeatedly trounced by UB and most Generals.
The catch to Reg is, he has to put at least 2 points in any given skill for it to become a serious threat; compounding this, he has several passives that are almost necessities. Because of this, Reg generally will have 1 skill that's powerful and 2 or 3 that are quite weak. Unlike other DGs who can fall back on their other abilities when one is ineffective, Reg is something of a one-trick pony: if it turns out that the enemy is using a strat/has a natural advantage against whatever your one strong skill is, you're pretty much %&$# outta luck.
For example, Snipe is generally poor damage and huge mana cost, and is usable only for ganking; if the enemy is careful to carry a combat potion to chug only when they're in the crosshairs, Snipe doesn't work so great. If the Reg dumps points into Snipe to compensate, that's only aggrivating the problem, as he is now far behind in strengthening his other skills.
If he uses Wings, his damage is now respectable, but not great. Any DG with a combat trick--stun, life drain, slow, etc--will be able to overcome this. The problem is, at least 1 rank of Wings is almost necessary for farming purposes, or just bringing his damage up to par, so this is generally not a good investment.
Mark can be very effective, but makes Regulus almost entirely reactive--he has to rely on enemies using skills and triggering it to deal significant damage; this is a less-than-effective strategy in and of itself when any DG there is can beat Reg by just autoattacking on him. On top of that, this skill strains Reg's already piddlesome mana to its breaking point--not a good idea.
Mines are the most dangerous of Reg's abilities, but they nonetheless have their weaknesses. First and foremost, don't approach a mine-using Reg from any normal direction--i.e., think about where YOU would throw mines if YOU were the Reg, and don't go that way. If you have to go the long way around, all the better--he might get more damage on that tower, but by the time he spots you, he doesn't have mines to save him, and he has to go THROUGH you to escape; on top of that, if he's attacking your towers, he must therefore be far from his, which means he's in for a long and painful--possibly lethal--walk back.
As for mines used in combat, if he throws them away from you, watch them, and assume he will try to lead you over them. Pre-empt this by re-positioning yourself. If he throws them at you, take advantage of the long cast time and cooldown animation to run--not away, but AT him. Now he's only made things worse for himself, losing his precious 15-meter safety gap, and now there aren't mines between you and him, either. In all instances, generals foil mines handily--simply send minions forward to set them off, then charge.
Individual strats aside, notice that all of Regulus's abilities have a common feature: they work best when there is nobody to interfere with him, and work best by surprise. Reg is a lot like Batman: he may not be as strong or as fast as his super-powered compatriots, but give him enough time to prepare, and he can win any fight. Therefore, the best way to beat him is to deny him that precious prep time--a feat that can be accomplished by harassing him from multiple angles. Although he can fight decently well 1-on-1 (assuming preparations), he is extremely useless when outnumbered, barring lucky mine shenanigans. I doubt you would have a hard time convincing teammates to gang up on him--it may sound weird, but one of Reg's biggest weaknesses is that he is annoying, making him easy to hate, and easy to rally foes against him.
Ultimately, it's a matter of knowing his capabilities, his plan, and what tools your DG has to use against him. A long time ago, some old jerk named Sun Tzu said: "Know your enemy and yourself, and you need not fear the outcome of a hundred battles. Know only yourself, and for each victory you will also suffer a defeat. Know neither yourself or your enemy, and you will be destroyed in every encounter."
