I'm trying to add a video from Vimeo but the shortcode doesn't seem to be working.
Shouldn't all these shortcodes work on a self hosted install of wordpress?
They should, but unfortunately that's not the case. There's a specific problem with the Vimeo shortcode that means it only works on hosted wordpress.com sites.
In the meantime, while it's hopefully getting fixed, you can use this custom plugin to embed Vimeo videos into your post.