If you have the LM34 package itself in direct sunlight, then I can easily believe a 40º increase over ambient. Black heats up considerably in direct sunlight. Black is black because it's absorbing all wavelengths of light, reflecting none of them, which causes black objects to rise in temperature when in direct sunlight. On the flip side white is white because it reflects all wavelengths of light. That's why you see exterior thermometers of nearly any variety painted white.
So, paint the sensor white and/or keep it in the shade. I'd personally do both.