Common Lisp noob problem

(defvar *beep* '((A . Apple) (B . Ball) (C . Carrot)))

(defun apply-change (state k v)
  (let ((my-state state))
    (setf (rest (assoc k my-state)) v)
    my-state))

I want to take an a-list as input, create a temporary copy local to this function and modify one of the values (given a key) of the copy, and then return the copy.  But when I try this, it also modifies *beep* itself.

[1]>(apply-change *beep* 'C 'COCKS)
((A . APPLE) (B . BITCH) (C . COCKS))
[2]> *beep*
((A . APPLE) (B . BITCH) (C . COCKS))

How do I copy the alist in apply-change, instead of making my-state refer to the original?  And you can tell me the correct vocabulary I should be using here, too.