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.
Saving without metadata in Photoshop
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.
Saving without metadata in Lightroom
Unfortunately Lightroom isn't quite as easy. We need to install a specific Lightroom plugin that wipes all of the metadata and prepares the file correctly. There is a fantastic plugin written by the same person who wrote the tool mentioned above, it's just a bit fiddly to get installed.
To install the plugin, go to the website for Metadata Wrangler (that's what it is called) and click the download link under 'latest download'. Then you need to install it into Lightroom. To do that, go to the File menu -> plugin manager. In that window, click the 'add' button and choose the plugin file you just downloaded. More installation instructions here.
After it is installed, you'll see that you have additional options in the export dialog box in Lightroom. Here are the settings we'd recommend:
Unfortunately the "Include" box in the Lightroom provided metadata option does leave things like thumbnails embedded, which can be problematic. If you are exporting photos for other purposes, you can disable the Metadata Wrangler plugin either on the left hand side ("post process actions") or by unticking the 'enable' box.
The plugin we recommend is a "donationware" plugin, but it does allow processing of 10 images at a time. If you are wanting to do tons at once and strip the metadata, throw $5 Jeffrey's way as thanks for making a great plugin (or $0.01 if you want). You can see the information about registering here. We don't have any relationship with him and don't get any kickbacks or anything like that – it's just the best tool for the purpose!
If you're very cheap, at the very least set it to include "copyright only" and hopefully you won't see any problems. However if you see more errors like that, you might need to just spend the $5.