No comprendo por qué quieres mostrar el porcentaje en un label aparte, cuando se puede mostrar en la misma barra.

Pero bueno, si es eso lo que quieres, usa un ChangeListener:
http://docs.oracle.com/javase/7/docs/api/javax/swing/JProgressBar.html#changeListener

Si quieres saber cómo funciona internamente la JProgressBar, las distribuciones del JDK incluyen el código fuente de todas las clases. Con el change listener no necesitas crear tu propia implementación.

Por otra parte, ya has planteado antes problemas con JProgressBar, y no has comentado cómo te ha ido, ni si los ejemplos y soluciones te han servido para algo.

Como lo veo venir... sigue un test de ejemplo sobre cómo usar el ChangeListener para lo que quieres. Usa un JTextField, en vez de un JLabel, porque los textfield son más apropiados para valores que cambian.

import java.awt.EventQueue;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.JFrame;
import javax.swing.Timer;
import javax.swing.event.ChangeEvent;
import javax.swing.event.ChangeListener;

public class Test extends JFrame {

private static final long serialVersionUID = 2_477_557_509_637_393_421L;
private int contador;

public Test() {

initComponents();

final Timer timer = new Timer(500, new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
if (contador <= jProgressBar1.getMaximum()) {
jProgressBar1.setValue(contador);
contador++;
}
}
});
timer.start();

jProgressBar1.addChangeListener(new ChangeListener() {
@Override
public void stateChanged(ChangeEvent ce) {
jTextField1.setText(Integer.toString(jProgressBar1.getValue()));
if (contador > jProgressBar1.getMaximum()) {
timer.stop();
}
}
});

}

@SuppressWarnings("unchecked")
// <editor-fold defaultstate="collapsed" desc="Generated Code">
private void initComponents() {

jProgressBar1 = new javax.swing.JProgressBar();
jTextField1 = new javax.swing.JTextField();

setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE);
getContentPane().setLayout(new java.awt.FlowLayout());
getContentPane().add(jProgressBar1);

jTextField1.setEditable(false);
jTextField1.setColumns(3);
jTextField1.setHorizontalAlignment(javax.swing.JTextField.CENTER);
jTextField1.setText("0");
getContentPane().add(jTextField1);

pack();
}// </editor-fold>

/**
@param args the command line arguments
*/
public static void main(String args[]) {
EventQueue.invokeLater(new Runnable() {
@Override
public void run() {
new Test().setVisible(true);
}
});
}
// Variables declaration - do not modify
private static javax.swing.JProgressBar jProgressBar1;
private javax.swing.JTextField jTextField1;
// End of variables declaration
}

Es tan fácil como aplicar el método artimético para calcular el porcentaje de una cantidad, en el listener del JTextField.

Aquí jProgressBar1.getValue() se devuelve el valor que tiene, en cada instante, la barra.
Y aquí se obtiene el valor máximo jProgressBar1.getMaximum()
El resto es una simple operación artimética.

La idea del test era mostrar como usar componentes y listeners, no dar una lección de aritmética elemental ;D

import java.awt.EventQueue;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.JFrame;
import javax.swing.Timer;
import javax.swing.event.ChangeEvent;
import javax.swing.event.ChangeListener;

public class Test extends JFrame {

private static final long serialVersionUID = 2_477_557_509_637_393_421L;
private int contador;

public Test() {

initComponents();

jProgressBar1.setMaximum(500);

final Timer timer = new Timer(250, new ActionListener() {
@Override
public void actionPerformed(ActionEvent e) {
if (contador <= jProgressBar1.getMaximum()) {
jProgressBar1.setValue(contador);
contador++;
}
}
});
timer.start();

jProgressBar1.addChangeListener(new ChangeListener() {
private String porciento = "%";

@Override
public void stateChanged(ChangeEvent ce) {
jTextField1.setText(Integer.toString((jProgressBar1.getValue() * 100) / jProgressBar1.getMaximum()).concat(porciento));
if (contador > jProgressBar1.getMaximum()) {
timer.stop();
}
}
});

}

@SuppressWarnings("unchecked")
// <editor-fold defaultstate="collapsed" desc="Generated Code">
private void initComponents() {

jProgressBar1 = new javax.swing.JProgressBar();
jTextField1 = new javax.swing.JTextField();

setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE);
getContentPane().setLayout(new java.awt.FlowLayout());
getContentPane().add(jProgressBar1);

jTextField1.setEditable(false);
jTextField1.setColumns(6);
jTextField1.setHorizontalAlignment(javax.swing.JTextField.CENTER);
jTextField1.setText("0%");
getContentPane().add(jTextField1);

pack();
}// </editor-fold>

/**
@param args the command line arguments
*/
public static void main(String args[]) {
EventQueue.invokeLater(new Runnable() {
@Override
public void run() {
new Test().setVisible(true);
}
});
}
// Variables declaration - do not modify
private static javax.swing.JProgressBar jProgressBar1;
private javax.swing.JTextField jTextField1;
// End of variables declaration
}

Quizás con un tipo long sería suficiente, y los cálculos más rápidos.

http://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html

Si lo vas a resolver con BigInteger, te sugiero que lo codifiques así:

jProgressBar1.addChangeListener(new ChangeListener() {
private String porciento = "%";
private BigInteger T = BigInteger.valueOf(100);

@Override
public void stateChanged(ChangeEvent ce) {
final BigInteger V = BigInteger.valueOf(jProgressBar1.getValue());
final BigInteger M = BigInteger.valueOf(jProgressBar1.getMaximum());
jTextField1.setText(String.valueOf((V.multiply(T)).divide(M)).concat(porciento));
if (contador > jProgressBar1.getMaximum()) {
timer.stop();
}
}
});

porque el valor 100 es constante, y no necesitas calcularlo con cada disparo del listener.