How about more variety in level objectives? as well as levels.

Ie. Chuckie Egg, collect all the eggs to win levels etc.

You've all played Burger Time, right? Just checking.

I think a Viewtiful Joe-style 2.5D system would be as close to 3D as I'd want Donkey Kong to be. Being able to run around the barrles would be a total drag, and making them thirty-foot logs would defeat the purpose.

Make the girl prettier. Those eight pixels were not enticing enough to make it worthwhile.

New levels would be good. There weren't always barrels, for instance. The second level had those lousy rubber duck things that were (nearly) impossible to jump over.

Resist the temptation to add a boatload of power-ups. The hammer is enough.

And for the record, he wasn't Mario back then. He was Jumpman. The Mario name didn't come around until Mario Brothers, when the two-player simultaneous feature required differentiable guys. Hence the colors and names.

Donkey Kong '94 has 96 levels (more or less in the style of the original).