apt-get update fails with " Clearsigned file isn't valid, got 'NOSPLIT'"

Question

I am having this issue with a brand new Ubuntu 16.04.2 Virtual Machine.

apt-get updates fails with this error

$ sudo apt-get update -o Debug::Acquire::http=1 -o Debug::pkgAcquire::Auth=true -o Debug::Hashs=trueenter 
0% [Connecting to archive.ubuntu.com]GET /ubuntu/dists/xenial/InRelease HTTP/1.1
Host: archive.ubuntu.com
Cache-Control: max-age=0
Accept: text/*
User-Agent: Debian APT-HTTP/1.3 (1.2.19)


Answer for: http://archive.ubuntu.com/ubuntu/dists/xenial/InRelease
HTTP/1.1 200 OK
Content-Type: text/html; charset="utf-8"
Content-Length: 2832
Connection: Close

Get:1 http://archive.ubuntu.com/ubuntu xenial InRelease [2,832 B]
0% [1 InRelease 2,832 B/2,832 B 100%]201 URI Done: http://archive.ubuntu.com/ubuntu/dists/xenial/InRelease
ReceivedHash:
        - SHA512:9a57e33cddb5b821ee529e7e4e39d1039f260b1b3ceee28902b7e595dfcb95280f87f45a88f433b452657f725c6a61ee06e1d2ff12db8aac7a60e61286377232
        - SHA256:1c54e2c305d7254cc3c3fb5cc5651064094e7cbff00e8f4a4e1932536864f240
        - SHA1:eebbd844edee49449c7bdf6c1dc6243a85970544
        - MD5Sum:c0fdedc4ecc16c0bce32d264006d74e2
        - Checksum-FileSize:2832
ExpectedHash:

Err:1 http://archive.ubuntu.com/ubuntu xenial InRelease
  Clearsigned file isn't valid, got 'NOSPLIT' (does the network require authentication?)
Fetched 2,832 B in 0s (4,827 B/s)
Reading package lists... Done
E: Failed to fetch http://archive.ubuntu.com/ubuntu/dists/xenial/InRelease  Clearsigned file isn't valid, got 'NOSPLIT' (does the network require authentication?)
E: Some index files failed to download. They have been ignored, or old ones used instead.

I have verified that

• DNS is working correctly
• Tried Google DNS servers in /etc/resolv.conf
• /etc/network/interfaces has the correct values
• I am able to access http://archive.ubuntu.com/ubuntu/dists/xenial/InRelease using wget -O-
• No firewall configured (iptable shows ALLOW for both IP4 and IP6)
• Tried disabling IPV6 on the server level
• $http_proxy is blank

Now I am completely at loss as to why am I getting Clearsigned file isn't valid, got 'NOSPLIT' (does the network require authentication?)

What else can I try?