When do you loosen your straps? Is it in the beginning or after your feet go numb? Typically, your feet will swell as you ride. I put on my shoes kind of loose before I get on my bike, as I ride the swelling fills in to a good spot. I often have this problem with my rugby boots though. I will tie them too tight and my feet will go numb during a game. I will loosen them, but it will take a while before enough blood gets to wherever it gets to make them not numb again.
Try not strapping in so tight at first and see if that helps.