I was annoyed at having to hatch multiple eggs to find a nature, so I figured this one out using a little trial and error:
Instant egg (replace XX to choose nature)
94000136 fffe0000
b2101d40 00000000
e0001840 00000005
XXba0f8e 00000002
d2000000 00000000
XX) Nature
01) Rash
02) Timid
03) Lonely
04) Quiet
05) Impish
06) Quirky
07) Modest
08) Docile
09) Sassy
0a) Jolly
ob) Naughty
0c) Calm
0d) Hasty
0e) Brave
0f) Bashful
10) Lax
11) Hardy
12) Mild
13) Relaxed
14) Careful
15) Naive
16) Bold
17) Gentle
18) Serious
19) Adamant
Well, it's not a complete solution. I noticed that the natures repeat in the same pattern on up (1a rash, 1b timid...), repeating over and over again. If you do the math, the a1 that was in the original code (which always gave naughty) is right where naughty should be in the 97-af range. I also tested 10 ralts, 5 adamant using 19, 5 adamant using 32. Most everything seemed random, stats, their best IV, but they all had syncronize, not one had trace as an ability.
So, that still needs to be figured out I think, but otherwise this works like a charm...
~Baron_Fel