Here's the thing: Logistics tends to win or lose Barbarossa for all but the most experienced players.
Without knowing what you sent into the Ukraine, it's hard to diagnose the problem. Here are some potential pointers:
1) Put the highest skill general you can find at Army Group. If you have more than one theater, make sure all Army Groups have skill 5 generals or better. The general skill in this class will improve logistcs for all subordinate units in range.
2) Stack Logistics Wizards at Theater, Army Group, Army, and even Corps if you have enough of them. The effects stack. (Do take note that higher level HQs have less impact on individual divisions with traits, but affect more units. Consult the chain of command effects on the wiki or game manual for more information)
3) Reduce the number of active units in the area. Always remember that most expensive units (armor, artillery) tend to also have higher supply and fuel costs.
4) Take ports along the coast and manually set convoys to them. If the Italians seal the Med, and you own ports on the Med, send convoys to the Crimea, too.
5) Take Leningrad ASAP and use it as a supply point. It's a great port and can ship in tons of supplies. It can also be taken from the sea, providing a nice additional place to invade that doesn't involve walking from Warsaw to Moscow.
6) Put cabinet ministers into power than reduce supply consumption and increase supply throughput. Germany has some; use them.
7) Set your occupation policy to Collaboration Government to minimize partisan impact on supply. Seriously, don't antagonize the locals.