LoginToboggan Unified

I ran across the same issue and ended up implementing a combination solution in both the Checkout Redirect and LoginToboggan modules. The changes that I made are as follows. Hope this helps.

Checkout Redirect

function commerce_checkout_redirect_commerce_checkout_router($order, $checkout_page) {
    global $user;

    if (!$user->uid) {
        drupal_set_message(t('You need to login or create a new account in order to validate your order'), 'status');
        if (module_exists('logintoboggan')) {
            drupal_goto('user/login?destination=checkout');
        } else {
            drupal_goto('checkout/' . $order->order_id . '/user/register');
        }
    }
}

LoginToboggan

function logintoboggan_page_alter(&$page) {
    // Remove blocks on access denied pages.
    if (isset($page['#logintoboggan_denied'])) {
        //Change to check to see if the Commerce Checkout Redirect item has set the status message and set the message accordingly.
        if (!array_key_exists('status', drupal_get_messages())) {
            drupal_set_message(t('Access denied. You may need to login below or register to access this page.'), 'error');
        } else {
            drupal_set_message(t('Please login or create a new account in order to continue.'), 'status');
        }
        // Allow overriding the removal of the sidebars, since there's no way to
        // override this in the theme.
        if (variable_get('logintoboggan_denied_remove_sidebars', TRUE)) {
            unset($page['sidebar_first'], $page['sidebar_second']);
        }
    }
}

Here's a patch to allow commerce redirect to check for logintoboggan and use that for the login screen rather than the core.

Incorrectly tagged my post..

This patch is very useful but redirect on checkout page doesn't work very well, because of drupal_goto() "polluting" the URL argument. With the next correction it works like a charm on my test site.

drupal_goto('user/login', array('query'=>drupal_get_destination()) );

Please use the branch 2 version of the module.
I think will also cover this issue.