New DS features like the party battle system make this game totally worth it.
The story in this game involves Lan and his friends gathering at SciLab so that his father can show them all something, but before he can, Nebula attacks the lab with knockout gas and kidnaps Lan's dad and steals the PET's from Lan's friends. Lan was safely hidden in his father's cubicle because he was looking for his dad's ID when the gas hit. Before passing out from the gas Lan hears the PA system say that several areas of the net have been occupied by a mysterious group. Several days after this Lan receives an anonymous email saying SciLab computers were under attack and he rushes out there only to find it wasn't under attack but that [Protoman or Colonel] was testing him to see if he is worthy to join a team to resist Nebula. Lan and MegaMan join and the adventure starts.
This game introduces liberation missions which sort of add a turn based strategy game into MMBN. They can be fun but can also be very frustrating at times, especially the later optional ones in the Nebula Areas. The way they work is that there are Dark Panels all over the area, they surround Dark Holes, which serve 2 purposes: to protect the Darkloid and to release guardians onto the field, and sometimes contain items, like zenny, battle chips, order points, or bug frags, and sometimes traps disguised as items. Most Navis have a special command they can use to aid in liberating more than one Dark Panel at a time, such as Protoman's Wide Sword and Colonel's Screen Divide hitting 3-squares wide. Not all have such a command, Magnet Man has Magnet Barrier which protects all team mates from Darkloid attacks for that turn and Knight Man has no command at all in exchange for always taking 0 damage from Darkloid attacks and automatically guarding any ally near him. Numberman and Searchman both have abilities that allow them to search out items. Toad Man and Meddy both have abilities that allow for liberating many panels in one turn. Gyro Man bombs 1 dark panel without having to fight and Shadow Man can use Sneak Attack on guardians and Darkloids, both of them can move over Dark Panels as well. Tomahawkman can clear a 2x6 grid while Napalmman can clear a cross pattern 5 squares ahead, both destroying all items except barrier keys in the process. Mega Man's liberation command is Long Sword which clears 2 panels. To use these commands, you must use up 1 order point, which you start with 3 and can have a maximum of 8 at any time. Also on the field are bonus panels which can provide anything an item panel can but also it can deal a major hit to the closest guardian or darkloid or it can grant invincibility for one turn to all your allies. The number of Dark Panels around your Navi will determine which side has how many panels in battle, and if you're completely surrounded it will be 2 colums for the enemy on each side with your Navi in the 2 colums in the middle (you can switch which way you're facing with R or L) A battle in liberation missions must be completed in 3 turns (when the custom gauge fills, and it opens automatically) or the liberate will fail. Battle is otherwise the same on a 3x6 grid.
The different Navis on each team is enough to want to play both versions but in addition to that, on the DS version you get several benefits to having both games finished, such as getting to fight an even harder version of Bass. In liberation missions, you can use something called a Transport chip to bring in the other team's member of the same position (i.e. Colonel Protoman, Shadowman Gyroman, Numberman Searchman, Toadman Meddy, Knightman Magnetman, Tomahawkman Napalmman). In the DS version you can use maps (picked up from BMDs in or near the corresponding area) and the Party Battle System which lets you carry 2 'images' of your team mates with you through the net, they can even be slightly customized with the Party Customizer. There's new Numberman Codes for various items, specifically the previously unobtainable Leader's Raid and Lord of Chaos chips. Also you can get a wide number of special effects by inserting MMBN 1, 2, 3, 4, or 5, Boktai 1 or 2 into the GBA slot (Boktai 3 and MMBN 4.5 as well if you're playing the JP version) for things like special shops, Sol Cross MegaMan and Bass Cross MegaMan and changing the battle music to a remixed version of the previous games' musics. I've also heard (but not confirmed myself yet) that you can get the other team's Navi chips from Higsby's open space board for 30,000 zenny each.
Graphics in this game are the same as they were in MMBN4 but the sound is vastly improved, especially the remixed battle music when you have the older games in the GBA slot.
This game does have its downsides, most notably there are more typos and "wrong mugshots" used than there were in mmbn3 and mmbn4 combined. Also liberation missions can get on your nerves very easily, especially if you try to get the super prize (from beating the mission in at least 2 turns less than the target). To add to all that you must S-Rank all the Omega Navis of your team mates to even be able to face the sub bosses of the secret areas.
I would reccommend this game to anyone, its extremely fun and has just the right amount of challenge.