Aid Another is not broken...
That perception check example you give, its supposed to work that way 100 percent. Conceivably the players could also just stand in a room and continue to roll perception checks until they get a number they like. If the situation has no inherent danger punishing a failed skill roll should have no consequences.
A creature can affect a particular check only once using the aid another action. However, up to four creatures can use aid another to affect a single check.
In certain circumstances, the DM might decide that only fewer than four creatures—or even no creatures—can try to aid a check. For instance, it is unlikely that more than one creature can assist in picking a lock.
From the Compendium all 5 of the other party members can't help at once and there are some guidelines for limiting it further due to physical necessity (you can't have 5 people trying to pick a lock at the same time, for example).
Also, in case you missed it, Aid Another's difficulty is:
DC: The assisting creature makes a skill check or an ability check against a DC equal to 10 + one-half its level.
Don't modify the core rules of Aid Another
At best a player can only add +2 if their role is successful and they could in fact make it harder by (-1) if they fail. Don't increase or decrease the bonuses. You can however restrict availability as you see fit and also dictate which skills or Stats are applicable to help out.
Create skill challenges & skill checks in combat that force different players to do different things at the same time
A classic example would be needing to close a portal to hell while hellish minions spew out of it. Anyone in the party can take a standard action to try to do an arcana check to start closing the gate, but then they aren't attacking. Likewise anyone who is aiding them is also loosing out on their standard action.
The pure skill challenge might consist of a situation where all of the PCs need to be doing something to solve the problem and their are real consequences on the line. Perhaps the inn caught fire and now they are trying to rescue everyone inside, have players take turns 1 at a time describing what they are doing to try to help and increment against them the effects of the fire as things get worse. Failure may mean they save one less person, take damage, or valuable items are lost to the flames, but helping someone else will cost you a turn in the skill challenge.