I finally found the solution (and 12 hours later support suggested the same...). What was happening was that the M-Audio driver's files were being installed, but it wasn't installed as a driver for the keyboard. The generic Windows drivers were being used instead.
What I did was I went into the Control Panal->Administrative Tools->Computer Management->Device Manager->Sound, Video and Game Controllers, right-click the "USB Audio Device" (Window's name for the keyboard) and select "Update Driver". Point it towards the "MA_CMIDI.DLL" file. When it's done plug in the keyboard and you'll get the New Hardware Installation Wizard they talk about in the "manual".
Thanks for trying!
PS Yeah should have given the OS from the start!