Did you ever forget to write "immediate" after shutdown when trying to stop a database? When this happens Oracle waits for all connections to terminate before shutting down which usually takes ages. Oracle obviously disallows the creation of new processes so if you try to shutdown the database again using the immediate keyword you will receive the "Not connected to Oracle" message. To recover from this situation you have to open another session and startup force the database and then shut it down again using shutdown immediate.