Fist, please note that the Percona Server natty repository is probably not going to receive updates any more, as Ubuntu will make natty unsupported very soon. If you check the available packages, you will see that the lastest stable version for natty is "5.5.23-rel25.3-240" while the lastest version for lucid or precise is "5.5.27-rel28.1-296", with some important security updates. I would advice you to choose a recent LTS version to avoid some nasty bugs in earlier versions of MySQL.
percona-server-server is a metapackage that depends on the latest PS version. You can choose to install either percona-server-server-5.1 or percona-server-server-5.5. Please be aware that Percona conflicts with MySQL official package, so it will uninstall it. Check the validity of the repositories. As an alternative, you can download manually both the .debs and .bin of the PS server and client.
PS 5.5 should work better than 5.1, but you should test any software upgrade beforehand, as it may break your particular application (no matter if you change to a new major version of Percona, Oracle's MySQL or MariaDB). Running mysql_upgrade after install should resolve most incompatibilities at server level, but you should read carefully the release notes for the particular version to see any 5.1 -> 5.5 changes. Please note that replacing the exact same versions of MySQL and PS should be safe with the default configuration. There are no changes on the client software.