"DB Error: unknown error" in CiviMail upon adding recipient group

Click Mailing | New Mailing
Specify recipient email group
Recipients status says "Estimating".
In a few seconds top-right status says "Saving"
After ~2 minutes with no change in these status indicators I get a popup:
Error
DB Error: unknown error

If recipient group is small (e.g. 2 contacts) sometimes there is no error. It seems that the more contacts that are in the group, the more likely it is to fail. With 4500 contacts, it fails every time. I'm not sure but I believe that if the auto-save starts while the contacts are being counted, then it will eventually time-out with the error. Perhaps there is a deadlock caused by the simultaneous auto-save and contact-counting processes.

No problem observed on 4.6.1 demo, but could test only with the 24 contacts existing on that system. The demo server is much faster than my VPS in counting the recipients. Perhaps this is because my system contains ~6000 contacts.

From log (note the "Lock wait timeout exceeded; try restarting transaction"):
Apr 12 01:36:44 [info] $backTrace = #0 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/CRM/Core/Error.php(894): CRM_Core_Error::backtrace("backTrace", TRUE)
#1 [internal function](): CRM_Core_Error::exceptionHandler(Object(DB_Error))
#2 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/packages/PEAR.php(931): call_user_func((Array:2), Object(DB_Error))
#3 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/packages/DB.php(976): PEAR_Error->PEAR_Error("DB Error: unknown error", -1, 16, (Array:2), "UPDATE civicrm_mailing SET domain_id = 1 , reply_id = 8 , unsubscribe_id = ...")
#4 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/packages/PEAR.php(564): DB_Error->DB_Error(-1, 16, (Array:2), "UPDATE civicrm_mailing SET domain_id = 1 , reply_id = 8 , unsubscribe_id = ...")
#5 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/packages/DB/common.php(1905): PEAR->raiseError(NULL, -1, NULL, NULL, "UPDATE civicrm_mailing SET domain_id = 1 , reply_id = 8 , unsubscribe_id = ...", "DB_Error", TRUE)
#6 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/packages/DB/mysql.php(899): DB_common->raiseError(-1, NULL, NULL, NULL, "1205 ** Lock wait timeout exceeded; try restarting transaction")
#7 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/packages/DB/mysql.php(328): DB_mysql->mysqlRaiseError()
#8 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/packages/DB/common.php(1216): DB_mysql->simpleQuery("UPDATE civicrm_mailing SET domain_id = 1 , reply_id = 8 , unsubscribe_id = ...")
#9 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/packages/DB/DataObject.php(2442): DB_common->query("UPDATE civicrm_mailing SET domain_id = 1 , reply_id = 8 , unsubscribe_id = ...")
#10 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/packages/DB/DataObject.php(1345): DB_DataObject->_query("UPDATE civicrm_mailing SET domain_id = 1 , reply_id = 8 , unsubscribe_id = ...")
#11 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/CRM/Core/DAO.php(444): DB_DataObject->update()
#12 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/CRM/Mailing/BAO/Mailing.php(1573): CRM_Core_DAO->save()
#13 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/CRM/Mailing/BAO/Mailing.php(1691): CRM_Mailing_BAO_Mailing::add((Array:31), (Array:2))
#14 [internal function](): CRM_Mailing_BAO_Mailing::create((Array:31))
#15 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/api/v3/utils.php(1284): call_user_func_array((Array:2), (Array:1))
#16 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/api/v3/Mailing.php(67): _civicrm_api3_basic_create("CRM_Mailing_BAO_Mailing", (Array:31))
#17 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/Civi/API/Provider/MagicFunctionProvider.php(89): civicrm_api3_mailing_create((Array:30))
#18 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/Civi/API/Kernel.php(96): Civi\API\Provider\MagicFunctionProvider->invoke((Array:9))
#19 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/api/api.php(23): Civi\API\Kernel->run("Mailing", "create", (Array:30), NULL)
#20 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/CRM/Utils/REST.php(402): civicrm_api("Mailing", "create", (Array:30))
#21 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/CRM/Utils/REST.php(638): CRM_Utils_REST::process((Array:3), (Array:28))
#22 [internal function](): CRM_Utils_REST::ajax()
#23 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/CRM/Core/Invoke.php(278): call_user_func((Array:2))
#24 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/CRM/Core/Invoke.php(86): CRM_Core_Invoke::runItem((Array:12))
#25 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/CRM/Core/Invoke.php(54): CRM_Core_Invoke::_invoke((Array:3))
#26 /var/www/clients/client1/web3/web/civicrm/sites/all/modules/civicrm/drupal/civicrm.module(489): CRM_Core_Invoke::invoke((Array:3))
#27 [internal function](): civicrm_invoke("ajax", "rest")
#28 /var/www/clients/client1/web3/web/civicrm/includes/menu.inc(519): call_user_func_array("civicrm_invoke", (Array:2))
#29 /var/www/clients/client1/web3/web/civicrm/index.php(51): menu_execute_active_handler()
#30