Technically this is an interesting one.
Officially the National Governing Body of the sport, currently 'British Ice Skating' has a coaching program and level exams/certification. These qualified coaches can be checked by calling the office or looking here ->
http://www.iceskating.org.uk/index.cfm/work-force-coaching/coaching/british-ice-skating-licensed-coaches-levels-1-5/When somebody wants to do a BIS level I'm not sure if a coach must be specified on the entry form, or it could be a different one to the one doing the actual teaching.
But technically anybody could be a coach. In the UK they would need to be checked for working with children/vulnerable adults, and it would be a good idea to have some First aid certification and professional indemnity insurance; the other main issue is clearing the coaching with the facilities where the coaching is taking place.
This probably happens more often than you'd think too - professional skaters might not have up-to-date valid BIS coaching credentials, visiting overseas coaches for skate camps, chorographers etc.
Take the Skate Excellence skating programme; I'd not sure what are the requirements are to qualify as a coach for this?
AnabelleMom - it probably depends on what service was advertised that you entered into contract with?