Interesting. I wonder what your random sequence was that Robetta couldn’t find anything.
Anyway, scientifically speaking, here is what I would do. Make a sequence that is weighted toward the secondary structures of your starting backbone structure. eg use a lot of alanines for helical regions, hihg-beta propensity residues for your sheets, etc. This will be more work than making a random sequence, but it will give you fragments that are weighted towards the same secondary structure as your starting backbone, thereby biasing you to staying near that structure – making smaller adjustments as you want, rather than large random changes.
Also, you can make fragments yourself using the make_fragments script included with rosetta++. If you are up for doing that, you can play around with the sequences you use as input, and get different fragment files out – some may give you better design results than others. Just depends how much work you want to do.