" Since mine only came with 12,…"
12..what? Have a dig around the "Presets" folder inside your Photoshop folder. There are other things in there, like in the "Textures" folder. If they didn’t get loaded when you installed Photoshop, have a look on the install disk. But Textures aren’t the same as Patterns.
That "rust" image you refer to isn’t a pattern, per se. It’s just an image. I would consider at pattern an image that can be tiled so that the edges blend seamlessly, left to right and top to bottom.
Now, if you’re after images that you can use for texture and overlay, there are plenty available.
Here are a couple of good ones, for starters:
<
http://www.textureking.com/>
<
http://textures.forrest.cz/>
Keep in mind that not every image you find online is free for your use in any commercial work. (See the notice at the bottom of the "textures.forrest.cz" link, above.) Some are, some aren’t. To know, you must explore the site and read. Usually, people who offer images will say very explicitly whether they are free or not.
If they’re just for your own personal, not-for-profit amusement, well, nobody can stop you from doing anything you want with anything you find, right?
And if you truly want patterns, well, that’s a different search entirely.
Try Google, eh? Maybe enter the search string Photoshop patterns free or something similar.