This seems to be an ongoing issue that is still reproducable in the latest Ubuntu Vbox 6.x.
The default NAT Network range is usually 10.0.2.0/24. If you change this range it does not seem to work properly.
Say we change the range to 10.50.1.0/24
If you get a new lease you will find that you get an IP from the old range but the default gateway is from the new range.
Delete this Network from Nat Networks and create a brand new one with the correct range and assign the new Nat Network to your VMs with the range that you wanted. There is some sort of bug that prevents VBOX from handing out the updated range.