Photoshop has a habit of saving additional "metadata" or information with photos when you edit them (e.g. to preserve the ability to edit layers, or colour profiles). This often doesn't cause many problems as internet browsers (etc) ignore this information or display it correctly, but Instagram is very particular about it.
The issue can cause upload errors or images not turning out as intended (e.g. having not quite the same colours as you originally thought). You can see whether your image has added metadata using this tool – the metadata we are talking about will appear under "APP14", "Photoshop", "XMP data" or similar.
The problem occurs when you use "Save" or "Save as" when saving your image to a JPG -- this will save the additional information. Photoshop provides another option under the File menu: "Save for web" or "Save for Web & Devices", which will save a standards-compliant JPG that should not give you any errors. The latest version of Photoshop (CC 2015) has it under File -> Export -> Save for web. You can also use a keyboard shortcut to access the window - ctrl + alt + shift + s (Windows) and cmd + opt + shift + s (Mac).
The "Save for web" dialog box should be configured something like this:
Make sure the 'quality' option is at 100, and progressive/optimised are off. Embed colour profile should be off, and tick the 'convert to sRGB' box – and metadata should be none.
Note: if you're using Photoshop CC 2015, you should actually use Export --> Export As... Read more about exporting from CC 2015.