I have cleared all my history in every way I can think off. Then I set Firefox to not remember anything. I really do intend for Firefox to not track and log my browsing habits. After these settings it appears to fix the "New Tab" screen (it now populates with generic icons) but if you dismiss one of the generic icons, Firefox will immediately populate the icons with my actual browsing history.