Can I use ido-completing-read instead of completing-read everywhere?

Edit: This is now an Emacs package available from MELPA. It has been expanded into a full-fledged minor mode. Development happens on GitHub.

Original post:

Here is my refinement of Jacobo's answer. Credit to him for the original magic. I've added an override variable, which you can use to prevent the use of ido-completing-read in specific functions. I have also added a check that uses the original completing-read if there are no completions (This happens occasionally, for example in org-remember-apply-template from org-mode, which breaks with Jacobo's original advice).

(defvar ido-enable-replace-completing-read t
  "If t, use ido-completing-read instead of completing-read if possible.

Set it to nil using let in around-advice for functions where the
original completing-read is required.  For example, if a function
foo absolutely must use the original completing-read, define some
advice like this:

(defadvice foo (around original-completing-read-only activate)
  (let (ido-enable-replace-completing-read) ad-do-it))")

;; Replace completing-read wherever possible, unless directed otherwise
(defadvice completing-read
  (around use-ido-when-possible activate)
  (if (or (not ido-enable-replace-completing-read) ; Manual override disable ido
          (boundp 'ido-cur-list)) ; Avoid infinite loop from ido calling this
      ad-do-it
    (let ((allcomp (all-completions "" collection predicate)))
      (if allcomp
          (setq ad-return-value
                (ido-completing-read prompt
                               allcomp
                               nil require-match initial-input hist def))
        ad-do-it))))

Oh, and for using ido in M-x, use amx.

Hocus pocus, abracadabra, presto!

(defadvice completing-read
  (around foo activate)
  (if (boundp 'ido-cur-list)
      ad-do-it
    (setq ad-return-value
      (ido-completing-read
       prompt
       (all-completions "" collection predicate)
       nil require-match initial-input hist def))))

That works with everything but subr's, from which execute-extended-command is the one that matters (what is binded to M-x). But we can get what we want from M-x

(global-set-key
 "\M-x"
 (lambda ()
   (interactive)
   (call-interactively
    (intern
     (ido-completing-read
      "M-x "
      (all-completions "" obarray 'commandp))))))