This seems to have been fixed in the latest package versions in Lucid 10.04.
Uname: Linux 2.6.32-10-generic i686
Packages: evince 2.29.5-0ubuntu1 poppler 0.12.3-0ubuntu1
Are you able to test with a Lucid 10.04 alpha 2 LiveCD and confirm? Note that after booting from the CD you will need to update the 3 poppler packages to the latest version.
This seems to have been fixed in the latest package versions in Lucid 10.04.
Uname: Linux 2.6.32-10-generic i686
poppler 0.12.3-0ubuntu1
Packages: evince 2.29.5-0ubuntu1
Are you able to test with a Lucid 10.04 alpha 2 LiveCD and confirm? Note that after booting from the CD you will need to update the 3 poppler packages to the latest version.