To use the new SPICE feature in Proxmox 3.1, you need to install a newer version of virt-viewer. At least on Ubuntu 13.04 the version I had, was to old. To remedy this I added this PPA:
sudo apt-add-repository ppa:dnjl/virtualization
sudo apt-get install virt-viewer