Yeah, you guys are right (for USCF at least). A move is completed *when you let go of your piece*. It's rule #15 in
here.
FIDE says that a move is "completed" when you hit the clock. USCF says that (at least in blitz, I'm not sure about standard) a move is "completed" when you let go of the piece.
Obviously you may begin your own move once your opponent completes his (whether he's hit the clock or not).
One thing I'm still not sure of is whether you may begin your move while your opponent is still touching his own piece? Do you have to let him "complete" his move before you begin yours? Of if he's holding his piece on a destination square but not letting go (still deciding if he wants to put it on that square or a different square) are you allowed to make your response move before he decides and lets go? Essentially "premoving" your response so that once he lets go and hits his clock all you have to do in response is hit your own clock, with your move already on the board?
Edit: And in FIDE, where "completing a move" requires hitting the clock, does this mean that my assertion of not being able to touch your own piece until your opponent hits the clock actually would be valid? And would only be an incorrect assertion under USCF rules? Or under FIDE rules would you still be allowed to touch your piece (begin your move) before your opponent's move is completed (the clock hit)?