For the sake of completeness & the archive:

The AKAI APC 40 works perfectly with Linux, it appears as a standard ALSA MIDI device. This is in line with the expectations since it is marked as a "standards complaint" MIDI device on Akai's homepage. There is a mention of a "proprietary handshake" there too, so I thought I'd clarify that: The handshake are special messages sent between the APC and Ableton's Live software. It has nothing to do with the MIDI compatibility of the device under any other circumstances.

As far as using the device goes, it is (IMO) quite brilliantly engineered, with some parameters remaining static, and other controllers having "banks" to switch between.
Eg: Master fader & crossfader stay static, while the lower right set of 8 endless encodes switches MIDI channel, while the CC's stay the same.
The Grid works in a similar manner, with each button (horizontally) sending the same note on, but on a different channel. Working with the device due to this fact is very easy, as one can do like so:
parameterSetFunction( 144 - midiByte1, midiByte2, midiByte3 );   // first arg is the track you want to call on

The controller / grid LEDs respond to the same MIDI message they send, wether that be a Note on or CC. Note that one must use the right channel to write to the right "bank" on the device.

Hoping to post a quick demo video using it with Linux soon, -Harry

PS: On a side note, its built like a tank, and the feel of the knobs & faders is fantastic :)