Why can't I change paredit keybindings

I'm trying to use just a few functions from paredit, without loading all the keybindings. Looking at paredit.el, the only keymap I found was paredit-mode-map, so I tried this.

(setq paredit-mode-map (make-sparse-keymap))
(define-key paredit-mode-map (kbd "<C-M-left>") 'paredit-backward)

It didn't change the keybinding (As checked with C-h k), but the variable paredit-mode-map was changed.

I also tried

(eval-after-load "paredit"
  '(progn
     (setq paredit-mode-map (make-sparse-keymap))
     (define-key paredit-mode-map (kbd "<C-M-left>") 'paredit-backward)))

and then turning paredit on and off, with the same result.

Previously, making changes to a keymap directly has always worked for me. What is going on here?

Edit:

I succeeded in changing the keymap by doing this:

; Remove old paredit bindings
(defun take-from-list (condp list)
  "Returns elements in list satisfying condp"
  (delq nil
    (mapcar (lambda (x) (and (funcall condp x) x)) list)))
(setq minor-mode-map-alist 
      (take-from-list 
        (lambda (x) (not (eq (car x) 'paredit-mode))) 
        minor-mode-map-alist))

; Create new paredit-mode-map
(setq paredit-mode-map (make-sparse-keymap))
(define-key paredit-mode-map (kbd "<C-kp-enter>") 'paredit-backward)

; Add the new paredit-mode-map to minor-mode-map-alist
(setq minor-mode-map-alist (append
                (list (append (list 'paredit-mode) paredit-mode-map))
                minor-mode-map-alist))

So it seems minor-mode-map-alist is a the variable used for lookup. I'm sure there are more elegant ways to change the keybindings, but I wanted to understand more of how keybindings work in emacs.