Adobe Utopia fonts are also available in CTAN:

ftp://ftp.funet.fi/pub/mirrors/ftp.tex.ac.uk/tex-archive/fonts/utopia

Here is their licence: readme.utopia

  Utopia-Regular
  Utopia-Italic
  Utopia-Bold
  Utopia-BoldItalic

  Permission to use, reproduce, display and distribute the listed
  typefaces is hereby granted, provided that the Adobe Copyright notice
  appears in all whole and partial copies of the software and that the
  following trademark symbol and attribution appear in all unmodified
  copies of the software:

        Copyright (c) 1989 Adobe Systems Incorporated
        Utopia (R)
        Utopia is a registered trademark of Adobe Systems Incorporated

Hi,

at least in the X.org CVS, the license of Adobe Utopia has been added.
See README and COPYING in

http://webcvs.freedesktop.org/xorg/font/adobe-utopia-type1/

The license looks non-free to me, but now Adobe Utopia could be added to
this package again.

cheerio
ralf