I just listened and there is definatly 4 beats, so no waltz...It sounds a lot like Salsa or Mambo (take your pick), but you could pull a samba out of the deep drum beats on 1 a 2, or a quick chacha, following the harmony of the horns.
It really depends on if you want to dance it what it is (Mambo/Salsa) or use it as a show piece and do what you want (ie; what dancing with the stars does to a lot of songs).
What ever you choose...don't do waltz.