As for scanning, which scanner do you have and what resolution are you scanning it at?

If using Photoshop 7, there is Filter - Pattern Maker. Image Ready has Filter - Other - Tile Maker. I think the Patter Maker was new in Photoshop 7 but Image Ready had Tile Maker for last version and version 7. There is also a set of plug-ins from Xaos Tools. Terrazzo is one of the plug-ins. It will do patterns. You can even pick from over a dozen symetry designs. I would have posted an example but it was hard to tell from your image how the pattern should have been repeating.