I'm using Dreamhost with PHP not as CGI and I'm not having any problems. That URL looks like it's using escaped characters, though I don't know why it would be doing that.
For example: drupal/user/485/edit?destination=admin/user becomes drupal/user/485/edit?destination=admin%2Fuser
drupal/user/481/edit/Personal information becomes drupal/user/481/edit/Personal%20information
But it's the first case to break Drupal (4.6.0), should I post it as a bug?