Why doesn't "composer update drupal/drupal" work?
Edit: this is probably not helpful b/c I just re-read your statement and you didn't have the same case as mine where I was coming from an old Drupal 8 install but I will leave this up in case anyone else has this issue and try to see if I can find the specific issue you are having. Sorry. 

I had this issue when dealing with a recent update and this was my issue but YMMV so if it doesn't work just let me know.

This may be a problem of that you composer file is set to the old repository listing on composer.org. Recently, Drupal setup their own composer endpoints, one for Drupal 7 and another for Drupal 8. You can read more about that change here: https://www.drupal.org/docs/develop/using-composer/using-composer-to-install-drupal-packages-through-drupalorg

This is the command that needs to be ran to swap the repository over the Drupal.org's. 

$ composer config repositories.0 
$ composer https://packages.drupal.org/8