Shipping Address Can't Be Added by User

Check the Permissions for the Site Group the User is a member of. If "Can edit their own personal account info” is set to Denied, they will not be able to submit an order. Because adding a shipping address is editing the Users shipping options, saving a new address will be blocked by this setting. Changing the permission to Allowed (which should be the case for this permission except in very rare situations) will permit the saving of new addresses.