Okay, I think I've recreated your situation locally and it appears that RubyMine has terrible support for managing remotes. If you create a Git repository locally, then (separately) create a repository on GitHub, there's no obvious way to marry the two from within RubyMine.
Basically, you need to set up GitHub as a remote for your local repository from the shell, and once that's done then RubyMine will be able to push as normal.
Please note that the below instructions assume you want to overwrite your GitHub repository with the full history from your local repository -- If your GitHub repository has data that you do not want to lose, do not execute these commands! See Below.
git remote add origin https://github.com/yourusername/yourrepo.git
git push -u origin +master
VCS > Git > Push
If your GitHub repository has already been committed to and you don't want to lose those changes, you'll need to either create a new GitHub repo or clone your GitHub repo into another folder and merge your local repository into the clone.
This can be avoided entirely if you're trying to push your existing local repository to a new GitHub repo: Simply use the VCS > Import into Version Control > Share project on GitHub option and use the dialog to create a new GitHub repository.
I forget to add that what you suggested above worked, although I did try that same syntax myself, with no success a couple of days ago. Perhaps I was still missing something. This is of course done outside RubyMine. I posted something that I think is a big in RubyMine on their dev discussion forum, a few hours ago, but so far I have not heard back.