In the photo gallery the max size is 500kb.. When I resize my pics on my kodak software I just choose the option that says resize to "best for web"
They come out smaller than I like sometimes but its an easy fix to get the uploaded. If your not using kodak just resize to smaller than 500kb.
Hope this helps.