Nel caso di operazioni "lunghe", sì generalmente "la soluzione" è il multi-threading. Poi tecnicamente ci sono diverse possibilità: uso diretto di Runnable/Thread, uso di SwingWorker (di serie da Java 6; specialmente se il "lavoro" deve aggiornare di tanto in tanto la interfaccia utente) oppure negli scenari più sofisticati i "thread pool" (di serie da Java 5).
Senza vedere il tuo codice comunque non posso dire più di tanto ma se ho intuito/interpretato bene il tuo scenario ... ripeto che la soluzione è l'uso dei thread.
Anzi ... la soluzione sarebbe che tu avessi (avuto) ben chiaro questi aspetti del threading in Swing, che sono fondamentali. Noto spesso invece che queste cose sono abbastanza ignorate/sottovalutate.