possibly the gain should be around 100x?
maybe u should try a higher input impedance?
like in figure 6 in that application report...
according to the LM358 datasheet
it might be a little inaccurate (Vio=3mV)...
if the input voltage difference is negative, u could try to swap the load cells (the output of the LM358 cant go lower than 5mV)...
did u try to measure the difference with a multimeter?
maybe u can c some little changes, that help u to find the correct gain...