Is that a fresh email address and the only place you ever used it was at Coinbase and you never used it ever before?
Yes and yes. It was only a few minutes old when I signed up. I have already changed my Coinbase email to another now as well.
Strange. I recently opened a Coinbase/GDAX account a couple months ago with an Outlook email address. Never used the email anywhere else. My inbox and spam folders are still completely empty... no sign of these two phishing emails.
So, if their database was compromised, then the phishers were unable obtain my email address. That's strange, given that it was created before yours. I'm guessing the OP's setup (or another service involved) is compromised, or that the story is just BS.
Really strange, maybe the computer is compromised, I have a Coinbase account for a few years now and never had any issue and did not receive any phishing emails recently.