Yep, we actually don't do any automatic order status updates on checkout completion or payment receipt. We don't really know what might need to be taken into consideration when updating order statuses or what statuses may even be available on a site, so we are purposefully agnostic in core.
The solution here is to use Rules to update the order status using one of two events: "When a customer completes checkout" or "When an order is first paid in full." The important distinction here is that depending on your payment method, it may be possible for a customer to complete checkout without payment. It may be off-line payment, a pending payment, or an asynchronous transaction that simply hasn't POSTed to your site yet.
For those reasons, if you're doing an order status update that triggers fulfillment or completion of an order, you should most likely be using the latter event to ensure the order has been paid in full before processing.
Note: if you prefer a code based solution instead, both of these events have corresponding hooks: