Why does composer not work with core composer.json file when adding new libraries?
Hope it helps someone else. The issue was that I only updated drupal's /core folder, not composer.json. So I had a very old composer file. When I updated it with the composer.json from the latest D8 download, things started working again.