There may be two reasons of this behaviour I can think of:
1. First - filesystem related. Write what fs is it, check dmesg output just after directory creation etc., but this is wrong way to go, because
2. Second - strange delays are *ALWAYS* DNS-related. Or NIS-related. And 30-second delay is like a fingerprint. And this is Ubuntu, so I am pretty sure about this. Check your NIS configuration: /etc/nssswitch.conf /etc/yp.conf etc. Unfortunatelly I have solved such problem only once and about two years ago and didn't have to do with Ubuntu server since.
Good luck,
backblaze.pl - reliable, hassle-free online backup