Starting SSIS Package through SSIS Catalog
I would agree with the comment from Travis Page. Having just gone through this is sounds like either the Service Principal Names(SPN) are missing for the SQL Service or the file share. Ultimately you will need the "MSSQL" SPN for your SQL Server instances and the "HOST" SPN for host of the fileshare. 

Some reading/blog articles to help understand troubleshoot any kerberos issues:

This blog describes the creation of SPN's using the SETSPN command line tool:
http://blogs.technet.com/b/tristank/archive/2006/05/08/spns-r-fn.aspx

There is a tool published from Microsoft which will help determine the SPN's require for SQL Server. This blog talks about the tool:
http://blogs.msdn.com/b/farukcelik/archive/2013/05/21/new-tool-quot-microsoft-kerberos-configuration-manager-for-sql-server-quot-is-ready-to-resolve-your-kerberos-connectivity-issues.aspx

Additionally there is this below article from Microsoft which will help troubleshoot any kerberos problems:
http://blogs.technet.com/b/askds/archive/2008/05/14/troubleshooting-kerberos-authentication-problems-name-resolution-issues.aspx