I got that error on .NET a couple of times, all involving accessing a recordset that was closed by the time I tried to read from it due a synchronization issue. Are you sure it is not throwing an exception when trying to connect the second time you open the tab? Add a delay before opening the second tab, or clear the cache; maybe the browser is trying to reuse the old applet and its connections the second time.

I was using destroy, but closing it in both stop and destroy doesn't affect it.

Pretty sure. Any exception is caught and printed with Exception.printStackTrace.

After opening it a second time and getting the error, I closed the tab and garbage collected from the Java console window. After that, I was able to use it again.
This is strange... Do I have to manually garbage collect somehow?

Edit:
Also, the console lists the error as occurring at DBConnection.search(DBConnection.java:145).
...But DBConnection.search begins at line 177. I'm quite confused now.

Edit 2:
Tested under both IE and Firefox, the problem is the same with both of them.
The class that connects to the database is a singleton, but it reconnects every time the program runs. Could it somehow be reusing the singleton?
Or could it be that the applet is still running until I reload the page, at which time it calls stop or destroy and closes the connection?

It seems that my error checks don't work for some reason.

public void createTable(DBTable table){
  try{
    //try to create the table (connection has already been made)
  }
  catch(MySQLNonTransientConnectionException e){
    instance=new DBConnection(); //something weird is going on, so reset the singleton
    createTable(table); //and call the method again.
  }
  catch(Exception e){
    e.printStackTrace(); //for other errors
  }
}

It never catches the MySQLNonTransientConnectionException.

Edit 3:
Interesting. It's able to function if I end the java.exe process before opening it a second time. But again, it only works in that tab.

Edit 4:
Even a manual garbage collect in the code fails to fix the problem.

public void stop(){
  if(!DBConnection.dead){
    DBConnection.instance().closeDatabaseVariables(); //close the connection, statements, and resultsets
    DBConnection.instance().die(); //set singleton instance to null
  }
  //garbage collect
  Runtime r = Runtime.getRuntime();
  r.gc();
  super.stop();
}
//destroy is the same

Any ideas?

I'm not very familiar with Java and have never written Java-based Web applications or Java applets, but I remember from The Clean Code Talks - "Global State and Singletons" that static members are shared by the entire JVM. In other words, they are stored on the class, not in the application, and subsequent runs of a given program will still share that same static value. So, while you may think your Singleton is new every time you access the page, it might very well be carrying over. It seems reasonable that a single JVM would be used for many applets. In other words, the browser probably wouldn't kill the JVM until it was sure no more applets were likely to be used and on subsequent accesses to the page would continue using state from previous executions (I'm purely speculating as I know very little about Java and even less in regard to applets). Rather than using a Singleton, you could try taking the advice given in the Google Tech Talk (which specifically mentions Java applets, IIRC) and rid your application of Singletons.

http://java.sun.com/products/plugin/1.3/docs/appletcaching.html

Now you're beginning to experience Java.

Have you tried searching the CLASSPATH for that class on those other computers?^[1] How is the CLASSPATH even set for applets?

** EDIT **

One Google result suggests wrapping your applet into a jar and creating a META-INF/MANIFEST.MF file with the applicable Class-Path entry. Then, use the archive attribute of the <applet> tag (apparently <applet> is depricated though, so here are instructions for using archives with the <object> tag) to embed the Java applet. My question then becomes what should you expect to be installed on the client and what should the client bring down from the server? Should standard-library code be expected on the client while all else brought down from the server? Should the class path first check on the client and then revert to the server? I don't know, but I'm sure there are best practices.

I figured it out! ...

... its cause you're using java.

Since you have some experience with "desktop" applications and considered that, did you consider using webstart? Web start Java apps are a sort of cross between applet and installed application. .NET ClickOnce is very similar or completely the same. The user starts the application in the browser, but then it is downloaded and run similar to a desktop app, although still within the security "sandbox" (SecurityManager). Web start process handles the update process very robustly, and can even be "installed" as a shortcut to the desktop, but I think this requires Internet connection to your application every time it is run to check for updates.