Power loss when cold

The problem I am having is when my truck is cold. After startup, I will start driving and my truck will be down on power. It will barely reach 50 mph on the freeway with black smoke coming out of the tailpipe for about 1-2 minutes. This happens at about 1/4 throttle. If I push the peddle farther, nothing happens. Once the temp gauge gets to halfway or normal operating temp, I will get full power. If I feel the power loss, I have pulled over, turned off the truck, restarted it and the problem is gone. My truck is a 2001 F-350 crew cab long bed, 7.3 powerstroke with auto trans, 6.5" pro comp lift with 35" tires, hypertech chip and a airraid intake. I don't get a check engine light when this occurs. This will even occur on a 70+ degree day. I feel it might be some type of coolant sensor, but that is just a guess.