You are getting this message because after reprojection the points that where on a regular grid in lat-lon are no longer a regular grid in another projected system. The reprojection step does not preserve the regularness because for a lot of projections the change between lat-lon and a projected system is not constant. So the distortion, or change, is larger in one area than in another, leading to a non-regular grid. Imagine the squares of the grid in lat-long becoming a non-square shape in a projected system.
The solution that is most simple is just to project the points to EPSG:4326 first, and then perform the interpolation step. I'm not sure which interpolation routine you use, but e.g. gstat does not support interpolation in lat-lon. So, going to a projected system, not lat-lon, before interpolating the data is always a safe bet.
If you really need to reproject a grid, some kind of interpolation needs to take place. You do two things: using a tool like gdalwarp
that can perform the coordinate transform and the subsequent warping of the resulting grid. Alternatively, you can interpolate the non-regular grid to a regular grid using e.g. nearest neighbor or any interpolation routine you like.