Perhaps your battery is weak and when you start the truck the line
voltage drops so low that the CD Player loses it memory. If this was
my truck, I'd have someone probe the battery terminals with a
voltmeter while I was starting the truck to see if the voltage drops a
lot. Another thing to try, before starting the truck, switch the
ignition switch to the accessory position and see if the MP3 player
starts from where it left off. I have owned several Fords in recent
years and all of them start playing CDs (and/or MP3s) from where they
were when I turned off the ignition switch.

Have you made any wiring modifications recently? Does your CD Player
include a clock? Does it retain the presets when you turn off the
truck?

Ed