I'm a bit unsure of your signs here; I think [110,1],[-249,1] might be a better basis for the lattice of (x,y) with x^3 + 15x^2y + 29xy^2 + 8y^3 == 0 mod 359

Might you be confusing the matrix-which-reduces-the-basis (which is what qflll() in Pari outputs) with the reduced basis?

Code:

? M=matrix(2,2)
%1 =
[0 0]
[0 0]
? M[1,1]=110
%2 = 110
? M[2,1]=1
%3 = 1
? M[2,2]=1
%4 = 1
? M[1,2]=-249
%5 = -249
? M
%6 =
[110 -249]
[1 1]
? redmat=qflll(M)
%7 =
[9 -7]
[4 -3]
? M*redmat
[-6 -23]
[13 -10]

and indeed [-6,13] and [-23,-10] appear to have f(x,y)%359==0.