Does it not even work on the default setting, like example.com/?p=123? Or is it just a problem with the default name & date based options?
Also, how did you move it? If you did a backup from an older version, I'm not sure if you'd hit problems importing it into a fresh install.
I'd make sure you have everything backed up, just in case things get too screwy.
I'd probably try running /wp-admin/upgrade.php to see if it need to update your DB.
Save up to $96 at Dreamhost with ALMOST97 promo code (I get $1).
Or save $97 with THEFULL97.