TL;DR: Set the ID of the IOrderAddress before setting it as ShippingAddress on the Shipment:

var shippingAddress = order.CreateOrderAddress();
shippingAddress.Id = "Shipping";
order.GetFirstShipment().ShippingAddress = shippingAddress;

Explaination

The new Order API (basically using only the interfaces) is a bit quirky sometimes. The current implementation of IShipment doesn't actually "have" any orders, the Shipment.ShippingAddress is just a setter that will go to the OrderGroup.OrderAddresses and set your address there and at the same time connecting it to the shipment by 

OrderAddress.Name = Shipment.ShippingAddressId

So the OrderGroup stores and manages all the orderAddresses and links it to Shipments. But IOrderGroup (new order API) doesn't implement the addresses, I think it's meant that you add the shippingaddresses on the shipment itself, which you are doing. However the underlying connection (the code snippet above) requires the Name of the address to be set. 

But IOrderAdress.Name, instead you can set the IOrderAddress.Id to something. The current implementation of IOrderAddress.Id property looks like this:

string IOrderAddress.Id
    {
      get
      {
        return this.Name;
      }
      set
      {
        this.Name = value;
      }
    }

That Name property seem familiar? :P Again, the new API is a bit quirky, it should probably be a bit clearer that every OrderAddress needs an ID before using it (Name in background).

That's good finding @Joel.

I'll see if we can make the way abstraction APIs are used better.

Regards,

/Q