Why does this example seem to contradict conservation of energy? Consider a 10 kg box on the bed of a truck accelerating at 1 m/s^2. Consider a reference frame where it starts at 0 m/s and ends at 10 m/s and then consider a reference frame where it starts at -5 m/s and ends at 5 m/s. The work is positive in the first reference frame and zero in the second. 
I am not sure how but I think this might be wrong. Consider the truck I think all reference frame can agree that amount of gas in truck has decreased due to combustion. So where does this energy go? Have we violated conservation of energy in this frame? I think not.
But how? how is energy conserved in this situation?  Where is the energy of combustion?
 A: The key to understanding how this works is to include the conservation of momentum and the mass of the earth as well. Let $m=10 \ \text{kg}$ and let $\Delta v = 10 \ \text{m/s}$. Then the change in KE of the mass $m$ is $$\Delta KE_m = \frac{1}{2}m (v_0+\Delta v)^2-\frac{1}{2}m v_0^2 = \frac{1}{2}m(\Delta v^2+ 2 v_0 \Delta v)$$ and the change in momentum is $$\Delta p_m = m (v_0 + \Delta v) - m v_0=m \Delta v$$ where different reference frames correspond to different choices of $v_0$. Note that the $\Delta KE_m$ depends on the reference frame (depends on $v_0$) and therefore the work does also. Note that $\Delta p_m$ does not depend on the reference frame. 
Now let $M$ be the mass of the earth and let $\Delta V$ be the earth’s change in velocity. By conservation of momentum $M\Delta V + m\Delta v = 0$ so $$\Delta V = -\frac{m}{M}\Delta v$$ So for the Earth $$\Delta KE_M = \frac{1}{2}M(\Delta V^2 + 2 v_0 \Delta V)$$ So again, the change in KE of the earth is frame variant, and therefore the work done on the earth is frame variant. 
Now, if we calculate the total change in KE by adding the change in KE of the earth to the change in KE of the truck and simplifying we get $$ \Delta KE_m + \Delta KE_M = \frac{m^2+mM}{2M}\Delta v^2$$ So even though the change in KE is frame dependent for both the truck and the earth and even though the work is therefore also frame dependent, the total change in KE of both the earth and the truck is frame invariant. 
This change in total KE is equal (in the ideal case) to the change in internal energy due to the combustion etc. So although the work is frame variant the total energy is conserved in all frames. Conservation and frame invariance are separate concepts, and when a frame variant quantity is conserved the conservation calculations must be performed in a single frame. To verify that the change in KE is equal to the change in internal energy one can change the car to a spring where the internal energy and the work are easy to calculate. 
A: It is indeed an oddity, but it is quite consistent. In the first reference frame work has been done moving the box. In the second, the box ends up where it started, no net displacement, no net work has been done, and no change to kinetic energy (although there has been a change to direction of motion). As anna v said in her comment '"conservation laws hold within inertial frames", and not between inertial frames"'
The fuel used does not enter into the question as phrased, because we are dealing here only with Newtonian mechanics, and because we are looking at only a part of a system. As Dale has explained, to restore the expected conservation laws we have to consider a frame describing the system, including the effect on the Earth's motion.
A: From the point of the guy who fuels the truck the reference frame that matters is the one where the road is stationary. because it is the road that the wheels work against to propel the truck.
A scooter riding thief traveling at a steady 5m/s relative to the trucks starting speed waits for the truck to match her speed before stealing the box that way she doesn't have to immediately cancel the kinetic energy of the box, because relative to her it is zero.
