I have never played Donkey Kong, until 5 minutes ago on http://www.donkey-kong.org/ They say "its fun", but I did not like it. Rage quit :-)
Maybe you can reverse the roles? Player plays Donkey Kong. Some AI plays Mario trying to reach the princess. Maybe add some bouncing barrels?