Comment 38 for bug 543266

With Ubuntu 10.04, ghostscript 9.01, and auctex-11.86-2ubuntu1 I had the same issue. To resolve I followed this

sudo dpkg -P --force-depends ghostscript
sudo apt-get install ghostscript

and then compile the latest AUCTeX Version manually using

http://theotp1.physik.uni-ulm.de/~ste/comp/emacs/auctex/snapshots/ftp/auctex-current.tar.gz

Using the source package from debian sid did not solve this problem. Installing the latest did. Note that you of course need to add this to your .emacs if AUCTeX is not loaded automatically

  (add-to-list 'load-path "/usr/local/share/emacs/site-lisp/auctex")
  (load "auctex.el" nil t t)
  (load "preview-latex.el" nil t t)