--- a/content/html/content/src/nsHTMLMediaElement.cpp
+++ b/content/html/content/src/nsHTMLMediaElement.cpp
@@ -1312,46 +1312,78 @@ public:
 
 typedef nsTHashtable<MediaElementSetForURI> MediaElementURITable;
 // Elements in this table must have non-null mDecoder and mLoadingSrc, and those
 // can't change while the element is in the table. The table is keyed by
 // the element's mLoadingSrc. Each entry has a list of all elements with the
 // same mLoadingSrc.
 static MediaElementURITable* gElementTable;
 
+#ifdef DEBUG
+// Returns the number of times aElement appears in the media element table
+// for aURI. If this returns other than 0 or 1, there's a bug somewhere!
+static unsigned
+MediaElementTableCount(nsHTMLMediaElement* aElement, nsIURI* aURI)
+{
+  if (!gElementTable || !aElement || !aURI) {
+    return 0;
+  }
+  MediaElementSetForURI* entry = gElementTable->GetEntry(aURI);
+  if (!entry) {
+    return 0;
+  }
+  PRUint32 count = 0;
+  for (PRUint32 i = 0; i < entry->mElements.Length(); ++i) {
+    nsHTMLMediaElement* elem = entry->mElements[i];
+    if (elem == aElement) {
+      count++;
+    }
+  }
+  return count;
+}
+#endif
+
 void
 nsHTMLMediaElement::AddMediaElementToURITable()
 {
   NS_ASSERTION(mDecoder && mDecoder->GetStream(), "Call this only with decoder Load called");
+  NS_ASSERTION(MediaElementTableCount(this, mLoadingSrc) == 0,
+    "Should not have entry for element in element table before addition");
   if (!gElementTable) {
     gElementTable = new MediaElementURITable();
     gElementTable->Init();
   }
   MediaElementSetForURI* entry = gElementTable->PutEntry(mLoadingSrc);
   entry->mElements.AppendElement(this);
+  NS_ASSERTION(MediaElementTableCount(this, mLoadingSrc) == 1,
+    "Should have a single entry for element in element table after addition");
 }
 
 void
 nsHTMLMediaElement::RemoveMediaElementFromURITable()
 {
+  NS_ASSERTION(MediaElementTableCount(this, mLoadingSrc) == 1,
+    "Before remove, should have a single entry for element in element table");
   NS_ASSERTION(mDecoder, "Don't call this without decoder!");
   NS_ASSERTION(mLoadingSrc, "Can't have decoder without source!");
   if (!gElementTable)
     return;
   MediaElementSetForURI* entry = gElementTable->GetEntry(mLoadingSrc);
   if (!entry)
     return;
   entry->mElements.RemoveElement(this);
   if (entry->mElements.IsEmpty()) {
     gElementTable->RemoveEntry(mLoadingSrc);
     if (gElementTable->Count() == 0) {
       delete gElementTable;
       gElementTable = nsnull;
     }
   }
+  NS_ASSERTION(MediaElementTableCount(this, mLoadingSrc) == 0,
+    "After remove, should no longer have an entry in element table");
 }
 
 nsHTMLMediaElement*
 nsHTMLMediaElement::LookupMediaElementURITable(nsIURI* aURI)
 {
   if (!gElementTable)
     return nsnull;
   MediaElementSetForURI* entry = gElementTable->GetEntry(aURI);
@@ -1426,16 +1458,20 @@ nsHTMLMediaElement::~nsHTMLMediaElement(
   NS_ASSERTION(!mHasSelfReference,
                "How can we be destroyed if we're still holding a self reference?");
 
   UnregisterFreezableElement();
   if (mDecoder) {
     RemoveMediaElementFromURITable();
     mDecoder->Shutdown();
   }
+
+  NS_ASSERTION(MediaElementTableCount(this, mLoadingSrc) == 0,
+    "Destroyed media element should no longer be in element table");
+
   if (mChannel) {
     mChannel->Cancel(NS_BINDING_ABORTED);
   }
   if (mAudioStream) {
     mAudioStream->Shutdown();
   }
 }
 
@@ -1946,16 +1982,17 @@ nsHTMLMediaElement::CreateDecoder(const 
   }
 #endif
   return nsnull;
 }
 
 nsresult nsHTMLMediaElement::InitializeDecoderAsClone(nsMediaDecoder* aOriginal)
 {
   NS_ASSERTION(mLoadingSrc, "mLoadingSrc must already be set");
+  NS_ASSERTION(mDecoder == nsnull, "Shouldn't have a decoder");
 
   nsMediaStream* originalStream = aOriginal->GetStream();
   if (!originalStream)
     return NS_ERROR_FAILURE;
   nsRefPtr<nsMediaDecoder> decoder = aOriginal->Clone();
   if (!decoder)
     return NS_ERROR_FAILURE;
 
@@ -1985,16 +2022,17 @@ nsresult nsHTMLMediaElement::InitializeD
 
   return FinishDecoderSetup(decoder);
 }
 
 nsresult nsHTMLMediaElement::InitializeDecoderForChannel(nsIChannel *aChannel,
                                                          nsIStreamListener **aListener)
 {
   NS_ASSERTION(mLoadingSrc, "mLoadingSrc must already be set");
+  NS_ASSERTION(mDecoder == nsnull, "Shouldn't have a decoder");
 
   nsCAutoString mimeType;
   aChannel->GetContentType(mimeType);
 
   nsRefPtr<nsMediaDecoder> decoder = CreateDecoder(mimeType);
   if (!decoder) {
     nsAutoString src;
     GetCurrentSrc(src);
@@ -2054,16 +2092,25 @@ nsresult nsHTMLMediaElement::FinishDecod
       rv = mDecoder->Play();
     }
   }
 
   if (OwnerDoc()->HasAudioAvailableListeners()) {
     NotifyAudioAvailableListener();
   }
 
+  if (NS_FAILED(rv)) {
+    RemoveMediaElementFromURITable();
+    mDecoder->Shutdown();
+    mDecoder = nsnull;
+  }
+
+  NS_ASSERTION(NS_SUCCEEDED(rv) == (MediaElementTableCount(this, mLoadingSrc) == 1),
+    "Media element should have single table entry if decode initialized");
+
   mBegun = true;
   return rv;
 }
 
 nsresult nsHTMLMediaElement::NewURIFromString(const nsAutoString& aURISpec, nsIURI** aURI)
 {
   NS_ENSURE_ARG_POINTER(aURI);
 

--- a/content/media/nsBuiltinDecoder.cpp
+++ b/content/media/nsBuiltinDecoder.cpp
@@ -197,22 +197,24 @@ nsresult nsBuiltinDecoder::Load(nsMediaS
       return rv;
     }
 
     mStream = aStream;
   }
 
   mDecoderStateMachine = CreateStateMachine();
   if (!mDecoderStateMachine) {
+    LOG(PR_LOG_DEBUG, ("%p Failed to create state machine!", this));
     return NS_ERROR_FAILURE;
   }
 
   nsBuiltinDecoder* cloneDonor = static_cast<nsBuiltinDecoder*>(aCloneDonor);
   if (NS_FAILED(mDecoderStateMachine->Init(cloneDonor ?
                                            cloneDonor->mDecoderStateMachine : nsnull))) {
+    LOG(PR_LOG_DEBUG, ("%p Failed to init state machine!", this));
     return NS_ERROR_FAILURE;
   }
   {
     ReentrantMonitorAutoEnter mon(mReentrantMonitor);
     mDecoderStateMachine->SetSeekable(mSeekable);
     mDecoderStateMachine->SetDuration(mDuration);
     
     if (mFrameBufferLength > 0) {