This is one of the first cryptocurrencies that I have seen that makes any substantial change to the traditional hashing model. As such, I wanted to understand the backing mathematics before trusting the coin. Thus far I have been underwhelmed by the quality of the documentation, so I would like to address the various aspects of Primecoin that make it unique, and to show how Primecoin continues to exhibit the attractive qualities of Bitcoin, pointing out where it may fall short. If anyone finds additional information then I would love to see it included here. I will do my best so answer questions, but I am new to this coin, just like everyone else. I will break down my analysis into addressing aspects of Bitcoin/Primecoin and describing how Primecoin goes about achieving the goal.
Proof of Work is "difficult," but verifying it is "easy"
For a proof of work coin it is necessary that the work being done takes some time. In particular, it is necessary that the solution to the work is much easier to verify than it is to find, such as is the case in NP compete problems. For Bitcoin and most other cryptocurrencies this is achieved by the use of cryptographic hash functions, where the output cannot be known without executing the hash; getting a hash with a specific quality requires guessing and checking, but verifying that a solution is correct only requires checking that one solution. In Primecoin the proof of work function is the primality of numbers. In mathematics it is conjectured that there is a lower bound on the computational power required to find a prime, which makes it a reasonably strong proof of work having been done. In the range that is being checked there are enough primes that a computer can discover dozens per second; it can verify far more in the same amount of time. Thus, primality serves as a valid proof of work function from this perspective.
It is also worth noting that for the range of primes being searched it is unreasonable for there to exist a "rainbow table" of sorts (precomputed list of primes to quickly check instead of generating new ones). There are simply too many primes.
Finding a block is not a global race; One cannot mine ahead of time
In order to allow people to mine it is necessary that finding the next block is not a global race. By this I mean that while faster computers can get more blocks, slower computers must still get some blocks. If the Primecoin protocol simply required a miner to find the next prime after a given number then the fastest computer wins. That is not how Primecoin works, though. In Primecoin, as I understand it, the previous block's hash is put together with data from the current block including data for a new transaction to the owner of the miner. All of this data is then hashed together to get a starting point, which I shall call H, for hash. Valid prime chains must start at H±1, 2H±1, 3H±1, etc. Since everyone has a different value for their transaction they will all have a different value for H, preventing the global race. Since H depends on the hash of the previous block it is impossible to start trying to find block N before block N-1 if found, short of guessing what the hash of block N-1 will be (which has heat-death-of-the-universe type of odds).
Tradeoffs between inflation, low fees, and security
Bitcoin was designed with the hopes of having no (or negative) inflation, while having low fees and good security. However, these aspects necessarily compete with each other: security is determined by how many people do work on the network; they cannot be expected to do work that costs them money, so they must either be paid in new money (inflation) or old money (fees), or else the system will not be secured by many miners. Trusting fees to work opens up a vulnerability to the tragedy of the commons (it is best for everyone if everyone includes a small fee, but it is best for an individual if they include no fee). Primecoin and others choose to take another path: by causing the coin to roughly follow a harmonic series where the reward for finding a block roughly follows a 1/x curve the total number of coins to be minted is unbounded, while still decreasing over time. This model has been used by other coins, and seems to work reasonably well, at least in the short term. Time will tell if it is a viable model over the long haul.
Difficulty Adjustments
One of the important features of Bitcoin is that the difficulty readjusts, allowing a more-or-less constant flow of mined coins. In hash based coins it is simple to adjust difficulty by setting a target number that the output of the hash must be less than. In Primecoin the difficulty is defined based on the length of a chain of prime numbers. There are three types of chain that are valid for Primecoin: Cunningham Prime Chains of the First and Second Kind, and Bi-twin Chains. Bi-twin chains are primes in the form N±1, (2N)±1, (4N)±1, etc., where all of the numbers are prime. Cunningham Prime Chains consist of the same sequence where the ± is replaced by either a + (first kind) or a - (second kind). For example, 2, 5, 11, 23, 47 is a Cunningham chain of the first kind of length 5 where N = 1.
For Primecoin the difficulty target specifies a length that the chain must have. If these lengths were very long (which they likely will be when/if this coin takes off) then this would give a sufficiently granular difficulty curve. However, for short chains there is too much difference between the difficulty of, for example, a chain of length 4 and a chain of length 5. To bridge that gap an additional fractional part is considered, based on a primality test. In this test a composite number will leave a residual that varies within a certain range; it varies somewhat uniformly--probably good enough to be used. Thus the fractional part of the strength of a chain is that residual divided by the max value it can vary over. This gives a much more continuous notion of difficulty requirements or the strength of a chain.
Another note is that rather than re-targeting difficulty once every 2016 blocks like Bitcoin, Primecoin readjusts difficulty every single block. This can make it more responsive to changes in mining power of the network.
Those are the biggest ways I've seen that Primecoin differs from Bitcoin, although I'm sure I've made mistakes and/or omissions. I'm happy to try my hand at answering questions, and would love to add more information as it becomes clear.