I took as my starting point Steve's observation that if (x+y) divides 16xy+1, it also divides (4y+1)(4y-1) and likewise divides (4y+1)(4y-1).

So (x+y) will divide the product of those terms and by the problem's gcd restriction it will divide (4x-1)(4y+1).

But that product = 16xy+4x-4y-1 = 16xy+4x+4y-8y-1 = (16xy+1)+(4x+4y)-(8y+2).

Then (x+y) factors (8y+2) and since (x+y) is odd--it equals 1mod16--dividing by 2 is OK which gives (x+y)*k = (4y+1) for integer k.

Now we're down to cases.  k=4 is already too big.  k=3 gives 3x=y+1, k=2 requires odd=even, and k=1 gives x=3y+1.

For k=3 (x+y)=(4x-1) and 16xy+1=(4x-1)(12x-1).

For k=1 (x+y)=(4y+1) and 16xy+1=(4y+1)(12y+1). 

Verifying the gcd requirement is easy but a little messy.  I expressed the two in terms of x or y then added and subtracted and divided out factors of 2 to get there.