I would agree that the shoe is probably flexing too much. That would be even more of an issue if as a new rider you were pedalling a bigger gear that requires you to push down through your foot harder. Try a stiffer soled shoe and try to use your gears as much as you can to keep your pedalling cadence high.
As others have mentioned, your saddle height/bike fit and circulation to your feet can all be factors too.
Living life like there's no tomorrow.
http://gorgebikefitter.com/
2007 Look Dura Ace
2010 Custom Tonic cross with discs, SRAM
2012 Moots YBB 2 x 10 Shimano XTR
2014 Soma B-Side SS