To summarize that bug report, here are the steps that produce deadlock:
1 - a thread holding one or more monitor locks causes an allocation failure.
2 - the garbage collector tries to flush the finalizer queue.
3 - a finalize() method (possibly via its calling chain) attempts to obtain one of the monitor locks that is already being held in 1.
4 - the finalizer thread from 3 blocks waiting on 1 (which is waiting on 3)
DEADLOCK

The problematic finalize() method for us is ColorModel.finalize(). By looking at the stack traces for our deadlock cases (one of which is pasted below), it shows that this method is executing in the finalizer thread, and that it is waiting for a monitor lock on an instance of sun.awt.image.PixelStore8, which is already owned by the image fetching thread.
Therefore, let me outline the exact steps that are producing our deadlock, using the steps listed above:
1 - The image fetching thread obtains the monitor lock for an instance of sun.awt.image.PixelStore8, and then causes an allocation failure.
2 - the garbage collector tries to flush the finalizer queue.
3 - ColorModel.finalize(), via its calling chain, attempts to obtain the monitor lock for the sun.awt.image.PixelStore8 instance that is already being held in 1.
4 - the finalizer thread from 3 blocks waiting on 1 (which is waiting on 3)
DEADLOCK

Unfortunately, because all this is happening deep within the JVM, we don't have the control required to implement a work-around. The attempted work-arounds I investigated were:
+ If we could detect when the deadlock occurred, we might be able to break the deadlock by interrupting the image loading thread, thereby releasing its lock and letting the finalizer continue. Unfortunately, I don't know of any way to get a hold of this thread so I can interrupt it.
+ If we could accurately predict when the garbage collector (gc) would likely get called while we were preparing to load an image, we could invoke the gc ourselves. Since the problematic monitor lock is obtained by the image loader, doing this beforehand would allow any ColorModels that were gc'd as a result of this explicit gc to successfully obtain the monitor lock. Unfortunately, in watching how the gc worked, it became obvious that we could not accurately predict when this would happen. Furthermore, there is no API in Java to determine the state of the gc.


------------------------------------------------------------------
Begin Stack Trace
------------------------------------------------------------------

Full thread dump:
    "Root Timer" (TID:0xe76838, sys_thread_t:0x7dc600, Win32ID:0xfff9a365, state:CW) prio=10
        COM.stagecast.playwrite.SystemTimer.run(PlaywriteRoot.java:2387)
        COM.stagecast.playwrite.FatalErrorNotifier.run(FatalErrorNotifier.java:52)
        java.lang.Thread.run(Thread.java:466)
    "AWT-Finalizer" (TID:0xe7e028, sys_thread_t:0x7c7510, Win32ID:0xfff9dfb1, state:CW) prio=8
        java.lang.Object.wait(Object.java:307)
        sun.awt.AWTFinalizer.run(AWTFinalizer.java:40)
    "Image Fetcher 1" (TID:0xe7de20, sys_thread_t:0x7c15b0, Win32ID:0xfff9dd79, state:CW) prio=4
        sun.awt.image.PixelStore8.allocateLines(PixelStore8.java:40)
        sun.awt.image.PixelStore.reconstitute(PixelStore.java:264)
        sun.misc.Ref.get(Ref.java:51)
        sun.awt.image.PixelStore.setPixels(PixelStore.java:88)
        sun.awt.image.GifImageDecoder.sendPixels(GifImageDecoder.java:450)
        sun.awt.image.GifImageDecoder.readImage(GifImageDecoder.java:558)
        sun.awt.image.GifImageDecoder.produceImage(GifImageDecoder.java:227)
        sun.awt.image.InputStreamImageSource.doFetch(InputStreamImageSource.java:257)
        sun.awt.image.ImageFetcher.fetchloop(ImageFetcher.java:143)
        sun.awt.image.ImageFetcher.run(ImageFetcher.java:119)
    "TimerQueue" (TID:0xe6ead0, sys_thread_t:0x7b1bb0, Win32ID:0xfff867b5, state:CW) prio=4
        netscape.application.TimerQueue.run(TimerQueue.java:174)
        java.lang.Thread.run(Thread.java:466)
    "Screen Updater" (TID:0xe6d318, sys_thread_t:0x7b3b30, Win32ID:0xfff94e4d, state:MW) prio=6
        sun.awt.ScreenUpdater.run(ScreenUpdater.java:91)
    "AWT-Windows" (TID:0xe6b558, sys_thread_t:0x799100, Win32ID:0xfff942a9, state:R) prio=5
        sun.awt.windows.WToolkit.run(WToolkit.java:98)
        java.lang.Thread.run(Thread.java:466)
    "AWT-EventQueue-0" (TID:0xe6b630, sys_thread_t:0x798350, Win32ID:0xfff94031, state:MW) prio=5
        java.awt.Graphics.getClipRect(Graphics.java:1099)
        netscape.application.ApplicationEvent.newUpdateEvent(ApplicationEvent.java:38)
        netscape.application.FoundationPanel.paint(FoundationPanel.java:112)
        sun.awt.windows.WComponentPeer.handleEvent(WComponentPeer.java:106)
        java.awt.Component.dispatchEventImpl(Component.java:1862)
        java.awt.Container.dispatchEventImpl(Container.java:949)
        java.awt.Component.dispatchEvent(Component.java:1741)
        java.awt.EventDispatchThread.run(EventDispatchThread.java:79)
    "Finalizer thread" (TID:0xe60088, sys_thread_t:0x78d680, Win32ID:0xfff99bed, state:MW) prio=2
        java.awt.image.ColorModel.finalize(ColorModel.java:113)
    "main" (TID:0xe600b0, sys_thread_t:0x78a7d0, Win32ID:0xfff963f1, state:CW) prio=5
        java.lang.ClassLoader.getSystemResourceAsStream(ClassLoader.java:351)
        java.lang.Class.getResourceAsStream(Class.java:630)
        COM.stagecast.playwrite.internationalization.ImageResources.fetch(ImageResources.java:399)
        COM.stagecast.playwrite.Resource.getImage(Resource.java:164)
        COM.stagecast.playwrite.PlaywriteRoot.displaySplashScreen(PlaywriteRoot.java:1602)
        COM.stagecast.playwrite.PlaywriteRoot.init(PlaywriteRoot.java:779)
        netscape.application.Application.run(Application.java:251)
        COM.stagecast.playwrite.PlaywriteRoot.main(PlaywriteRoot.java:667)
        com.stagecast.creator.Creator.main(Creator.java:52)
Monitor Cache Dump:
    sun.awt.AWTFinalizer@E7E028/EC6658: <unowned>
        Waiters: 1
    <unknown key> (0x7dc600): <unowned>
        Waiters: 1
    java.lang.Class@E6D208/ECC7A0: owner "Screen Updater" (0x7b3b30, 1 entry)
    sun.awt.image.PixelStore8@E74B30/F1D7A8: owner "Image Fetcher 1" (0x7c15b0, 2 entries)
    netscape.application.TimerQueue@E6C8D8/EC9AF8: <unowned>
        Waiters: 1
Registered Monitor Dump:
    Thread queue lock: <unowned>
    Name and type hash table lock: <unowned>
    String intern lock: <unowned>
    JNI pinning lock: <unowned>
    JNI global reference lock: <unowned>
    BinClass lock: <unowned>
    Class loading lock: owner "main" (0x78a7d0, 1 entry)
    Java stack lock: <unowned>
    Code rewrite lock: <unowned>
    Heap lock: <unowned>
    Has finalization queue lock: <unowned>
    Finalize me queue lock: <unowned>
        Waiters: 2
    Monitor registry: <unowned>