FULL PRODUCT VERSION :
java version "1.6.0-beta2"
Java(TM) SE Runtime Environment (build 1.6.0-beta2-b76)
Java HotSpot(TM) Client VM (build 1.6.0-beta2-b76, mixed mode)

build 74 and 75 show the same problem.

ADDITIONAL OS VERSION INFORMATION :
Generic swing problem.

A DESCRIPTION OF THE PROBLEM :
Upon closing a JInternalFrame, the JDesktopPane scans through the layers of the layerered pane in getFrames(). The new algorithm used is very slow in the case that one puts a component on very low or very high positions, so normally all layers up or down to 0 are scanned one by one. The result is that the closing of JInternalFrames in 1.6 gets very slow until completely impossible.

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
Just run the submitted case (although there's a JTree in it which is not displayed, it shows the problem). Just close the JInternalFrame and see...

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
The JInternalFrame is closed.
ACTUAL -
It's not closed, instead the JVM will seem to consume all available CPU time on the current CPU. Although it seems to do this infínitely, it doesn't... it just takes *ages*.

ERROR MESSAGES/STACK TRACES THAT OCCUR :
Stack trace is useless in that case.

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import javax.swing.*;
import java.awt.*;

public class DesktopPaneBug extends JFrame implements Runnable {

   private JDesktopPane dp;
   private JButton b;

   public static void main(String[] args) {
      new DesktopPaneBug();
   }

   public DesktopPaneBug() {
      super("DesktopPaneBug");
      SwingUtilities.invokeLater(this);
   }

   public void run() {
      Container cp=getContentPane();
      cp.setLayout(new BorderLayout());
      dp=new JDesktopPane();
      dp.setPreferredSize(new Dimension(400,300));
      cp.add(dp,BorderLayout.CENTER);

      JTree jt=new JTree();
      dp.add(jt,new Integer(Integer.MIN_VALUE)); // That's the problem now... Change that to -10 and the problem *seems* gone.

      JInternalFrame f=new JInternalFrame("Normal layer Frame, close me pls",true,true,true,false);
      f.setSize(200,100);
      f.setLocation(50,50);
        f.setVisible(true);
      dp.add(f,new Integer(0)); // That's the problem now... Change that to -10 and the problem *seems* gone.

      pack();
      show();
   }
}

---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
Don't use layers with very high or very low indexes. Which is not very good, as the predefined layer indexes for FRAME_CONTENT_LAYER is 30000, which obviously is already too much for the current algorithm.
I raise the severity to "difficult" as if you don't have the sourcecode of an application which traps into this, you're really stopped. This has to be fixed before final...