The only thing that works for me is putting the following in ~/.tmux.conf
# Allow xterm titles in terminal window, terminal scrolling with scrollbar, and setting overrides of C-Up, C-Down, C-Left, C-Right
set -g terminal-overrides "xterm*:XT:smcup@:rmcup@:kUP5=\eOA:kDN5=\eOB:kLFT5=\eOD:kRIT5=\eOC"
(you may need to reboot for this to take effect)
Update:
I found that if you change the setting in Putty Connection > Data > Terminal-type to "putty" (used to fix some formatting issues) from "xterm" then this solution stops working.
Update 2:
Use this if you want "putty" as your terminal type: set -g terminal-overrides "putty*:XT:smcup@:rmcup@:kUP5=\eOA:kDN5=\eOB:kLFT5=\eOD:kRIT5=\eOC"