Running phabricator/bin/storage upgrade should let you know to run it with --username <user> --password <pass> when attempting and failing to create new databases, if the mysql user doesn't have those permissions.
The upgrade documentation should at least reference the possibility.
Unfortunately no, it fell off the scrollback buffer. It was attempting to create database phabricator_spaces, and the mysql user it was using per the configuration didn't have access to do that.
I recreated the error:
# ./storage upgrade
Before running storage upgrades, you should take down the Phabricator web
interface and stop any running Phabricator daemons (you can disable this
warning with --force).
Are you ready to continue? [y/N] y
Applying patch 'phabricator:db.spaces'...
[2015-07-07 07:55:07] EXCEPTION: (AphrontAccessDeniedQueryException) #1044: Access denied for user 'phabric'@'%' to database 'phabricator_spaces' at [<phutil>/src/aphront/storage/connection/mysql/AphrontBaseMySQLDatabaseConnection.php:304]
arcanist(head=master, ref.master=d54cb072facd), phabricator(head=master, ref.master=6d404c821902), phutil(head=master, ref.master=fffe7e4ef4c8)
#0 AphrontBaseMySQLDatabaseConnection::throwQueryCodeException(integer, string) called at [<phutil>/src/aphront/storage/connection/mysql/AphrontBaseMySQLDatabaseConnection.php:275]
#1 AphrontBaseMySQLDatabaseConnection::throwQueryException(mysqli) called at [<phutil>/src/aphront/storage/connection/mysql/AphrontBaseMySQLDatabaseConnection.php:181]
#2 AphrontBaseMySQLDatabaseConnection::executeRawQuery(string) called at [<phutil>/src/xsprintf/queryfx.php:6]
#3 queryfx(AphrontMySQLiDatabaseConnection, string, string, string) called at [<phabricator>/src/infrastructure/storage/management/PhabricatorStorageManagementAPI.php:135]
#4 PhabricatorStorageManagementAPI::createDatabase(string) called at [<phabricator>/src/infrastructure/storage/management/PhabricatorStorageManagementAPI.php:185]
#5 PhabricatorStorageManagementAPI::applyPatch(PhabricatorStoragePatch) called at [<phabricator>/src/infrastructure/storage/management/workflow/PhabricatorStorageManagementUpgradeWorkflow.php:190]
#6 PhabricatorStorageManagementUpgradeWorkflow::execute(PhutilArgumentParser) called at [<phutil>/src/parser/argument/PhutilArgumentParser.php:406]
#7 PhutilArgumentParser::parseWorkflowsFull(array) called at [<phutil>/src/parser/argument/PhutilArgumentParser.php:301]
#8 PhutilArgumentParser::parseWorkflows(array) called at [<phabricator>/scripts/sql/manage_storage.php:176]