We have investigated this problem under Ubuntu 10.04 LTS (64-bit version).
Cause: When launching the debugger, Nios II IDE will search for source code in a number of locations, traversing all sub-folders of those locations. For some reason, the list of locations will include the user's home folder. If you have a lot of stuff there, you will have to wait. And wait...
Workaround: After killing and re-starting the Nios II IDE, do the following. From the Run menu, select "Debug...". In the left-hand pane, highlight the project you want to debug. The Nios II ISS configuration for your project should be shown. Click the Source tab, highlight your home folder, and click Remove. Now click Apply, then Debug.
Disclaimer: We found the workaround today. There may be other fixes or workarounds.
Credits: I'm a teacher at KTH and worked with technical staff at CSC, KTH, to find and fix this problem.