You should definitely be able to use UNA with VPS. You have more control in a VPS environment and will have to setup more things yourself or as LeonidS suggested, ask your hosting provider to help you. I have my own dedicated server for my site so I have to do everything.