I'm not really familiar with C++, but in regular C, a "feature" of most/all implementations is that, indeed, the random sequence is constant between launches of the program (allegedly, to simplify testing), so you need to feed srand a "random" number in the first place such as the time!
If the number ends up constant, the output of the following calls to "rand" will be the same...
...so, the questions are:
1- what is being fed to srand in the first place? (hopefully you can just display it somewhere for testing)
1 and half - what is time? something actually linked to the hardware clock, or something arbitrary (cpu cycles / number) since the start of the console/IOS/homebrew/thread?
2- is random_shuffle actually using rand, or at least its data source? (the example you linked clearly agrees)
3- is the DKPPC standard library, or whatever is providing the random functions, actually doing work conforming to the standard, or at least resembling it?