(Converting Ulrike's comments to an answer)
Assuming that you did run
updmap without the
--admin key: Update the FNDB with
initexmf -u, run
updmap --verbose then try again your font. If it doesn't work: Check which
updmap writes. Check if this it the map file your document use (see end of the log-file). Check if this
pdftex.map contains the entries of your map.
You have a multi user installation with an admin and a user mode. And in contrast to the widespread prejudice the admin mode is not the more powerful. In general, user settings (packages, configurations, map files, texmf trees, ...) take precedence over the default settings from the admin. What you do in user mode will normally work directly and without problems - but only for this user. What you do in admin mode will work for all user - as long as they don't have personal settings. See for more in Difference between administrative and user mode of MiKTeX.
Exactly the same happens on Unix systems. Running
updmap and not
updmap-sys (with superuser privileges) will leave a
pdftex.map in the user space that will have precedence over the system wide one. This may have undesirable effects in case of an update to the distribution that changes the font subsystem.
(from http://docs.miktex.org/manual/advanced.html, using problem cited in Font display error in windows, which produces the error
The mathkerncmssi source file could not be found.)
initexmf --edit-config-file updmap.
Insert the following line at the end of the file (relevant to the font in question):
Save the file and close the editor.
initexmf --mkmaps to rebuild the font map files.
For a general guidance see Manual font installation.