What version of NetBSD are you trying to install? I don't think host OS (i.e. Ubuntu) and your hardware have anything to do with it. Especially, if you said that you were able to install other OS's. It's Virtualbox. Another OS you can try is FreeBSD or OpenBSD. They are very closely related to each other.
Sorry, I'm not very big on BSD troubleshooting. I just prefer to use Mac
Try Xen or Vmplayer. Vmplayer (from Vmware) should definitely work. I think you can download some pre-made BSD images/appliances from Vmware site. Virtualbox will also play Vmware vmdk files. Also there is a hack way to make your own images on Vmplayer. But I won't go there yet!