Okay. I believe I've found a solution that has stood up to a few tests.
Extending Random gives you access to the protected method next(int). Using this steps the Random position. So by overriding the nextFloat/nextInt/etc methods and incrementing a counter. I can initiate a new Random object, using the same seed and a count and called next() enough times to catch up to the previous instance. Seems to work well and is a nice simple solution.
Thanks to those who answered/commented.