OLD SOLUTION
In /net/altera/mentor/max2/userware/default/dme, the file
dmgr_session_window.ample should have one line, which is:
$set_toolbox_search_path(["$MGC_HOME/toolbox","$MAX2_MENTOR/.toolbox"]);
This problem usually shows up, right after an altera upgrade.
NEW SOLUTION
Check the toolbox search path in $MGC_HOME/edg_ample_files/userware/dme/dmgr_session_window.ample
Since this file is no longer tied to Altera installations, this problem should disappear.