There are multiple reasons why the Ajax timeout message could be displayed, so the fact that it's so generic makes tracking an issue a little more difficult.
I made a few modifications so that the timeout message now gives details of what the timeout relates to.

includes/languages/English/checkout_one.php

Find (line 57)
Code:
define('JS_ERROR_AJAX_TIMEOUT', 'It\\\'s taking a little longer than normal to update your order\\\'s shipping cost.  Please close this message and try again.\n\nIf you continue to receive this message, please contact us.');
Replace with
Code:
define('JS_ERROR_AJAX_TIMEOUT', 'It\\\'s taking a little longer than normal to update your order\\\'s details (General Ajax Timeout error).  Please close this message and try again.\n\nIf you continue to receive this message, please contact us.');
define('JS_ERROR_AJAX_SHIPPING_TIMEOUT', 'It\\\'s taking a little longer than normal to update your order\\\'s shipping cost.  Please close this message and try again.\n\nIf you continue to receive this message, please contact us.');
define('JS_ERROR_AJAX_PAYMENT_TIMEOUT', 'It\\\'s taking a little longer than normal to update your order\\\'s payment method.  Please close this message and try again.\n\nIf you continue to receive this message, please contact us.');
define('JS_ERROR_AJAX_SET_ADDRESS_TIMEOUT', 'It\\\'s taking a little longer than normal to set your order\\\'s address.  Please close this message and try again.\n\nIf you continue to receive this message, please contact us.');
define('JS_ERROR_AJAX_RESTORE_ADDRESS_TIMEOUT', 'It\\\'s taking a little longer than normal to restore your order\\\'s address values.  Please close this message and try again.\n\nIf you continue to receive this message, please contact us.');
define('JS_ERROR_AJAX_VALIDATE_ADDRESS_TIMEOUT', 'It\\\'s taking a little longer than normal to validate your order\\\'s address details.  Please close this message and try again.\n\nIf you continue to receive this message, please contact us.');
define('JS_ERROR_AJAX_RESTORE_CUSTOMER_TIMEOUT', 'It\\\'s taking a little longer than normal to restore your customer details.  Please close this message and try again.\n\nIf you continue to receive this message, please contact us.');
define('JS_ERROR_AJAX_VALIDATE_CUSTOMER_TIMEOUT', 'It\\\'s taking a little longer than normal to validate your customer details.  Please close this message and try again.\n\nIf you continue to receive this message, please contact us.');

includes/modules/pages/checkout_one/jquery.checkout_one.js

Find (line 471)
Code:
 alert( ajaxTimeoutErrorMessage );
Replace with
Code:
alert( ajaxTimeoutShippingErrorMessage );
Find (line 639)
Code:
 alert( ajaxTimeoutErrorMessage );
Replace with
Code:
alert( ajaxTimeoutPaymentErrorMessage );
Find (line 700)
Code:
alert(ajaxTimeoutSetAddressErrorMessage);
Replace with
Code:
alert( ajaxTimeoutPaymentErrorMessage );
Find (line 796)
Code:
alert(ajaxTimeoutSetAddressErrorMessage);
Replace with
Code:
alert(ajaxTimeoutRestoreAddressErrorMessage);
Find (line 860)
Code:
alert(ajaxTimeoutSetAddressErrorMessage);
Replace with
Code:
alert(ajaxTimeoutValidateAddressErrorMessage);
Find (line 959)
Code:
alert(ajaxTimeoutSetAddressErrorMessage);
Replace with
Code:
alert(ajaxTimeoutRestoreCustomerErrorMessage);
Find (line 959)
Code:
alert(ajaxTimeoutSetAddressErrorMessage);
Replace with
Code:
alert(ajaxTimeoutValidateCustomerErrorMessage);

includes/modules/pages/checkout_one/jscript_main.php

Find (line 33)
Code:
var ajaxTimeoutErrorMessage = '<?php echo JS_ERROR_AJAX_TIMEOUT; ?>';
Add after
Code:
var ajaxTimeoutShippingErrorMessage = '<?php echo JS_ERROR_AJAX_SHIPPING_TIMEOUT; ?>';
var ajaxTimeoutPaymentErrorMessage = '<?php echo JS_ERROR_AJAX_PAYMENT_TIMEOUT; ?>';
var ajaxTimeoutSetAddressErrorMessage = '<?php echo JS_ERROR_AJAX_SET_ADDRESS_TIMEOUT; ?>';
var ajaxTimeoutRestoreAddressErrorMessage = '<?php echo JS_ERROR_AJAX_RESTORE_ADDRESS_TIMEOUT; ?>';
var ajaxTimeoutValidateAddressErrorMessage  = '<?php echo JS_ERROR_AJAX_VALIDATE_ADDRESS_TIMEOUT; ?>';
var ajaxTimeoutRestoreCustomerErrorMessage = '<?php echo JS_ERROR_AJAX_RESTORE_CUSTOMER_TIMEOUT; ?>';
var ajaxTimeoutValidateCustomerErrorMessage = '<?php echo JS_ERROR_AJAX_VALIDATE_CUSTOMER_TIMEOUT; ?>';
@lat9, please consider adding these edits to the master file set, if only to save me having to make them every time I do an update to this great module!