Your solenoid has a bad connection, check all of your cables and connections, and make sure it is mounted firmly to the fender. If the mounting holes are stripped out this problem will continue due to the bad ground connection. (chased this problem nearly 3 months, went through nearly a dozen solenoids!) The solution for me was to drill new mounting holes for the solenoid right next to the originals, and install new sheetmetal screws, had problem-free starting for a year!
Also, charge the battery before starting it again, the solenoids on our 5.0s are pretty sensitive, especially for the first few startups, they want a fully-charged battery, even 50 CCA less than factory will often keep it from working properly on the first start and lead to another failure later on.