Skin won't change using Minecraft.net, stuck as Alex

I have tried re-installing Minecraft (I even uninstalled the old version and deleted every minecraft file on my computer before reinstalling), but my skin is stuck as Alex.

I have tried changing my skin via Minecraft.net

I ran the command /give @p skull 1 3

{SkullOwner:"MYUSERNAME"}

and received an Alex skull (while imputing random usernames created a mixture of Alex and Steve skulls, and imputing specific usernames produced the proper skulls).

So I know that problem is specifically on my end.

Any thoughts on a solution?

Perplexed