Well, tried to make some clean ups so I could study the code better later.
Here's what I've got so far:

/**
 * Sequenzer
 * Mikael Fernstrom
 * 2013-02-20
 * This is a simple example. If you want to increase accessibility, 
 * add for example
 * key strokes to turn squares on/off, select channels etc., 
 * i.e. using keys instead or as 
 * a complement/alternative to mouse/touch interaction.
 *
 * For some background on high-precision timer threads, see:
 * http://processing.org/discourse/beta/
 * board_Syntax_3Baction_display_3Bnum_1213599231.html
 * For some background info on threads, see
 * http://forum.processing.org/topic/threads-how-they-operate
 *
 * http://forum.processing.org/topic/high-too-high-cpu-load-on-windoze
 * build #10
 */

import ddf.minim.*;

/**********************************************************************/

final Minim minim = new Minim(this);
final static byte BPMs = 120;
MidiThread midi = new MidiThread(BPMs);

final static byte numSounds = 16;
final static AudioSample[] player = new AudioSample[numSounds];

final static short numRects = 256;
final static int[] rectX = new int[numRects];
final static int[] rectY = new int[numRects];
final static boolean[] rectOver = new boolean[numRects + 1];

final static int rectSz = 25;            // Diameter of rect
final static int rectSpacing = 40;       // Distance between rectangles
final static int startX = 5, startY = 5; // Margin offset
final static int bpmLocX = 660, bpmLocY = 210;
final static color rectColor = #333333;  // ordinary rectangle colour
final static color rectHL = #BBBBBB;     // highlight colour
final static color bg = 0;               // background colour

boolean isPlaying;
float playerPos = 0;
int currPlay = 0;
//int prevPlay = -1;
int myBPM = 120;
int btnID = -1; // keep track of what button we're over

/**********************************************************************/

void setup() {
  size(800, 600); // size of the Processing window
  noLoop();

  playerPos = startX + rectSz/2;

  textFont( createFont("Georgia", 24) );  // loads font
  textAlign(LEFT);

  // calculate all rectangle coordinates
  for (int i=0, curX = startX, curY = startY; i!=numSounds; i++) {
    for (int j=0; j!=numSounds; j++) {
      rectX[i*numSounds + j] = curX;
      rectY[i*numSounds + j] = curY;
      curX += rectSpacing;
      // check if we've filled one row
      if (j == numSounds - 1)    curX = startX;
    }
    curY += rectSpacing;
  }

  // load the sound clips:
  for ( int i = 0; i != numSounds; 
  player[i++] = minim.loadSample(String.format("%02d", i) + ".mp3") );

  // let's start the MIDI thread for timing
  midi.start();
}

/**********************************************************************/

void draw() {
  // set background colour:
  background(bg);

  // draw a vertical line, indicating the player position:
  stroke(#00FF00);
  strokeWeight(5); // make the play cursor a wider line
  line(playerPos, 0, playerPos, height);

  playerPos = startX + rectSz/2 + rectSpacing*currPlay;

  // draw the rectangles
  stroke(#FF0000);
  strokeWeight(1); // draw thin lines around rectangles

  for (int i=0; i!=numSounds; i++)
    for (int j=0; j!=numSounds; j++) {
      fill(rectOver[i*numSounds + j] ? rectHL : rectColor);
      rect(rectX[i*numSounds + j], rectY[i*numSounds + j], rectSz, rectSz);
    }

  showBPM(myBPM); // show the current tempo on screen
}

/**********************************************************************/

// check for keyboard keys
void keyPressed() {
  // change play speed with arrowkeys, UP/DOWN
  final int k = keyCode;

  if (k == UP)   ++myBPM;    // increase tempo

  else if (k == DOWN) 
    if (--myBPM < 1)   myBPM = 1;  // decrease tempo

  //midi.stop();
  // we get thread death when the arrow buttons are held down
  midi.quit(); // stop the thread
  midi = new MidiThread(myBPM); // set the new bpm value
  midi.start(); // start the thread again

  // play/stop using the space bar
  if (k == ' ')    isPlaying = !isPlaying;

  // quit the program if we hit q
  else if (k == 'Q') {
    stop();
    exit();
  }
}

/**********************************************************************/

// handle mouse clicks
void mouseClicked() {
  update();  // check if we're over a rectangle:
  println(btnID);
  rectOver[btnID] = !rectOver[btnID];
  redraw();
}

/**********************************************************************/

// display BPM
void showBPM(int i) {
  fill(-1);
  text("Tempo", bpmLocX, bpmLocY);
  text(i, bpmLocX, bpmLocY + rectSpacing);
}

// update what button we're over
void update() {
  for (int i=0, idx; i!=numSounds; i++) {
    idx = i*numSounds;
    for (int j=0; j!=numSounds; j++, idx++)
      if (overRect(rectX[idx], rectY[idx], rectSz, rectSz)) {
        btnID = idx;
        return;
      }
  }
}

// check if the cursor is over a particuar area
boolean overRect(int x, int y, int w, int h) {
  return mouseX >= x & mouseX < x+w & mouseY >= y & mouseY < y+h;
}

// pick the notes that are active for the beat we're on
void soundStep(int n) {
  for (int i = 0; i != numSounds; i++)
    if (rectOver[n + i*numSounds])    player[i].trigger();
}

// shutdown the midi thread when the applet is stopped
void stop() {
  if (midi != null)     midi.isActive = false;
  super.stop();
}

/**********************************************************************/

// this is the thread running the timing
final class MidiThread extends Thread {
  // this is based on Toxi's code on 
  // http://processing.org/discourse/beta/
  // board_Syntax_3Baction_display_3Bnum_1213599231.html

  boolean isActive = true;
  int prevTime, interval;

  MidiThread(float bpm) {
    // interval currently hard coded to sixteenth beats
    interval = round(1000/bpm/15);
    prevTime = millis();
  }

  void quit() {
    isActive = false;
    interrupt();
  }

  void run() {
    try {
      while (isActive) {
        // calculate time difference since last beat & wait if necessary
        int nano = millis();
        float timePassed = (nano - prevTime) * 1e-6;

        while (timePassed < interval)
          timePassed = (nano - prevTime) * 1e-6;

        if (isPlaying) {
          // code to advance a step and play notes
          if (++currPlay >= numSounds)    currPlay = 0;
          soundStep(currPlay);
        }
        // calculate the time difference
        int timeDelay = ceil(abs(interval - (nano - prevTime) * 1e-6));
        prevTime = nano;

        // park the thread
        Thread.sleep(timeDelay);
      }
    } 
    // catch if in trouble
    catch(InterruptedException e) {
      //  println("force quit...");
    }
  }
}

/**********************************************************************/

Your version sucks MORE CPU% than my example, and, it doesn't play the sounds.

So sorry! Problem is that I've got some bugs in my WinXP that it doesn't play any sounds anyways! 
So I couldn't spot when it may have stopped working after the "refactoring"!

=== Minim Error ===
=== Likely buffer underrun in AudioOutput.

Gonna try to test the code in Linux to see if it works there!

Still need to understand how it works.
My doubts are about how many threads are necessary for your code to work.

midi = new MidiThread(myBPM);

Is it possible to just wake up and re-initialize current Thread rather than creating a new one?

Also I don't understand what is that 1e-6 for!

" Also I don't understand what is that 1e-6 for!"
I look only at the code above, I don't know the original code. But it looks a bit suspicious at this point:

        int nano = millis();
        float timePassed = (nano - prevTime) * 1e-6;

        while (timePassed < interval)
          timePassed = (nano - prevTime) * 1e-6;

I find strange than you put a time in milliseconds in a variable named nano, suggesting it is supposed to hold nanoseconds... There is a Java function giving current time in nanoseconds, but that's not this one.
The 1e-6 could convert nanoseconds to seconds, but  it might be overkill for milliseconds.
And the while loop might be the cause of CPU sucking: doing such loop tight doing nearly nothing is generally avoided. At best, you should put a delay(1); or similar inside, to be easy on the multitasked system (Windows might support this less than MacOS).