It's true, and you'd also have a hard time encoding two primes on a single atom. But the current estimates on the number of atoms in the universe vary pretty wildly, so it's not a bad guess.
If you really want a more accurate estimate of how much larger a universe we need, you first need to compute the number of composite numbers which are the product of two primes and are less than 2^768. Let K be the number of primes less than the square root of 2^768:
K = PI(root(2^768))
(where PI is the prime-counting function)
The number of composites, N, is "K choose 2", plus all the square numbers:
N = K!/2*(K-2)! + K
So that's the size of the number of values we actually want to store. Storage wise, assume we can store these all in a table sorted by the composite number, and then use a binary search to find the number we're looking for. (This is of course completely preposterous; while you'd only need to access lg(N) records to do a binary search, which is going to be way less than 768, your hard drive is going to take on the order of 10^230 square inches of space to store all this data, so it's going to take your read head a LONG time to do 768 reads all over the disk).
For the naive storage scheme, you'd need 3*768 bits to store each composite and it's two primes. The actual number of atoms you need is dependent on your storage medium. The average storage today for hard drives is around 250GBit/in^2. Stanford has managed a bit density of 35bit/electron with holographic storage technology, which is mighty impressive; you'd only need around 5 atoms per entry.
Then you need to pick which estimate of the number of atoms which exist in our observable universe you like best. :)