Terne is in
Debrecen, Hungary
Solving the nonogram yields
some kind of convoluted Rorschach test:
This is where the key comes in:
There are five yellow dots above the square and six blue dots below it. Counting the green 1 as both colors and decoding with A1Z26 we get:
in yellow: A, C, G, I, M
in blue: A, E, Q, R, S, U
so it's clearly a
MAGIC SQUARE!
Doing some quick maths, we get
this solution:
Now, if we
assign each number in the magic square to a 7x7 region of pixels in the nonogram and rearrange them in order, we get something much more recognizable:
The eight colored squares now clearly represent
the eight most populous cities in Australia: Sydney, Melbourne, Brisbane, Perth, Adelaide, Gold Coast, Newcastle, and Canberra.
The colors tell us to
index into each city's name by the index of each color using ROYGBIV:
syDney (yellow)
mElbourne (orange)
Brisbane (red)
peRth (yellow)
adElaide (yellow)
gold Coast (blue)
nEwcastle (orange)
caNberra (yellow)
That gives his location as
DEBRECEN, which is indeed about as far away from Australia as one can get!
Also (hat tip to @oAlt in comments):
Sequence mentions that he's feeling "peckish" - or in other words, Hung(a)ry!