How about something like this?
Don't draw your lighting by tinting your tile sprites. Draw your unlit tiles to a render target, then draw the tile lights to a second render target, representing each one as a grayscale rectangle covering the area of the tile. To render the final scene, use a shader to combine the two render targets, darkening each pixel of the first according to the value of the second.
This will produce exactly what you have now. That doesn't help you, so let's change it a bit.
Change the dimensions of your lightmap render target so that each tile is represented by a single pixel, rather than a rectangular area. When compositing the final scene, use a sampler state with linear filtering. Otherwise leave everything else the same.
Assuming you've written your shader correctly the lightmap should be effectively "scaled up" during compositing. This will get you a nice gradient effect for free via the graphics device's texture sampler.
You may also be able to cut out the shader and do this more simply with a 'darkening' BlendState, but I'd have to experiment with it before I could give you the specifics.
UPDATE
I had some time today to actually mock this up. The answer above reflects my habit of using shaders as my first answer to everything, but in this case they're not actually necessary and their use needlessly complicates things.
As I suggested, you can accomplish exactly the same effect using a custom BlendState. Specifically, this custom BlendState:
BlendState Multiply = new BlendState()
{
AlphaSourceBlend = Blend.DestinationAlpha,
AlphaDestinationBlend = Blend.Zero,
AlphaBlendFunction = BlendFunction.Add,
ColorSourceBlend = Blend.DestinationColor,
ColorDestinationBlend = Blend.Zero,
ColorBlendFunction = BlendFunction.Add
};
The blending equation is
result = (source * sourceBlendFactor) blendFunction (dest * destBlendFactor)
So with our custom BlendState, that becomes
result = (lightmapColor * destinationColor) + (0)
Which means that a source color of pure white (1, 1, 1, 1) will preserve the destination color, a source color of pure black (0, 0, 0, 1) will darken the destination color to pure black, and any shade of gray in between will darken the destination color by a middling amount.
To put this into practice, first do whatever you need to do to create your lightmap:
var lightmap = GetLightmapRenderTarget();
Then just draw your unlit scene directly to the backbuffer as you normally would:
spriteBatch.Begin(SpriteSortMode.Deferred, BlendState.AlphaBlend);
/* draw the world here */
spriteBatch.End();
Then draw the lightmap using the custom BlendState:
var offsetX = 0; // you'll need to set these values to whatever offset is necessary
var offsetY = 0; // to align the lightmap with the map tiles currently being drawn
var width = lightmapWidthInTiles * tileWidth;
var height = lightmapHeightInTiles * tileHeight;
spriteBatch.Begin(SpriteSortMode.Immediate, Multiply);
spriteBatch.Draw(lightmap, new Rectangle(offsetX, offsetY, width, height), Color.White);
spriteBatch.End();
This will multiply the destination color (unlit tiles) by the source color (lightmap), appropriately darkening unlit tiles, and creating a gradient effect as a result of the lightmap texture being scaled up to the necessary size.