I am about to upload on a 5-day delay the attached patch for this bug.
If you would rather fix it yourself you will know what to do.
diff -Nru sphinxsearch-2.0.4/debian/changelog
sphinxsearch-2.0.4/debian/changelog
--- sphinxsearch-2.0.4/debian/changelog 2012-04-20 03:50:21.000000000 +0100
+++ sphinxsearch-2.0.4/debian/changelog 2012-06-11 21:32:01.000000000 +0100
@@ -1,3 +1,10 @@
+sphinxsearch (2.0.4-1.1) unstable; urgency=low
+
+ * Non-maintainer upload.
+ * Removed hard-coded dependency on libmysqlclient16 (Closes: #676595)
+
+ -- Nicholas Bamber <nicho...@periapt.co.uk> Mon, 11 Jun 2012 20:31:53 +0000
+
sphinxsearch (2.0.4-1) unstable; urgency=low
* New upstream release.
diff -Nru sphinxsearch-2.0.4/debian/control sphinxsearch-2.0.4/debian/control
--- sphinxsearch-2.0.4/debian/control 2012-04-20 03:50:06.000000000 +0100
+++ sphinxsearch-2.0.4/debian/control 2012-06-11 21:34:39.000000000 +0100
@@ -7,7 +7,7 @@
Package: sphinxsearch
Architecture: any
-Depends: ${shlibs:Depends}, ${misc:Depends}, libmysqlclient16, adduser
+Depends: ${shlibs:Depends}, ${misc:Depends}, adduser
Description: Fast standalone full-text SQL search engine
Sphinx is a standalone full text search engine, meant to provide fast,
size-efficient and relevant fulltext search functions to other applications.
