Service Credentials to use in AlwaysOn Availability Groups?
When using AlwaysOn Availability Groups does each SQL Instance need to use the same service credentials?

No, SQL Server service accounts can be different. We have a 3 node cluster running AlwaysON and on all the servers SQL Server is running with a different account.
e.g. If you have one server in NY and other in LD, then

Active Directory Accounts to be created (Below will  be sql server service accounts)
NYDB1_sql
LDDB1_sql
Add both these accounts to the group DB1-SQL (below)
Active Directory Group to be created : DB1-SQL (Both the above accounts to be members of this group).

One important thing to note, from BOL :

If two server instances run as different accounts, the system administrator must use the CREATE LOGIN Transact-SQL statement to create a login for the startup service account of the remote instance in the syslogins table of the master database of each server instance.

Also, grant the CONNECT permission on the endpoint to the service accounts.

Previously we've had the SQL Server Service account locked out which has obviously caused problems.

You can use group managed service account - which are new in Windows Server 2012. The only requirement is you need at least one Windows 2012 domain controller, and use 2012 or 2012 R2 member servers.