After a fair bit of Google abuse and knowing that the solution lay somewhere in a UTF-8 character set, it came down to 2 things, and I thought I would share the solution for those who might also be struggling.
Firstly, I defined the utf-8 character set in the header response of my PHP API script:
header('Content-type: text/html; charset=utf-8');
That didn't work on its own, but it did solve the issue for characters that I manually echo'd from php, so I knew the problem had to be with the database.
I also had to define the character set for the database connection:
mysql_set_charset('utf8');
I defined this right after the connection to the database is made so that it applies to the last made connection. You can also define a specific connection.