I've been playing around and have found an even better method.
N.B. The neatline is the checked border. The graticule is the latitude and longitude lines.
1. Start with your map cropped to it's edges.
2. New layer, fill with a solid colour. Call layer 'Stroke'. Drag it to the bottom of your layer stack.
3. Increase canvas size to required width of neatline. (Image / Canvas Size. Relative checked, size increase in the boxes - both boxes should have the same number for a border of uniform width).
4. File / New. Size your image to 1000 px square. Fill with black (or whatever colour you want your neatline darks to be)
5. Increase canvas size by percentage: 100% in both directions. Relative checked, click any of the corner arrows. The black box will be in one of the corners of the larger canvas. Use the select tool, hold down Alt (make sure snapping is on) and drag a copy of the black box to the opposite corner so you have a chequerboard. Fill the remaining transparent pixels with white (if not already white) or whatever colour you want your neatline lights to be.
6. Save the file as a pattern (edit / define pattern). Chances are that this pattern will be suitable for any future maps you make, so you only need to make the pattern once.
7. Go back to your original image, make a new layer on the top and fill with a solid colour so it will take a layerstyle.
8. Layerstyle pattern fill with your new pattern. Use the scale slider on the pattern fill layerstyle to ensure that you have slightly more than the largest required number of divisions (check on the preview). If, for example I wanted to have 30 divisions across and 10 divisions down. I might end up with 35 and a bit checks across and 35 and a bit down. That's fine as I have at least 30 divisions. The shape of the divisions do not matter at this point, it is only the number that is important.
9. Make a new layer below the current layer and merge down to get rid of the layerstyle. (Call the new layer graticule).
10. Ctrl-T to transform and using the bounding boxes resize the chequerboard pattern so you have the required number of horizontal and vertical divisions. Make sure that the black and white checks fit exactly to the sides and corners.
11. The chequerboard pattern is going to be a bit blurry around the edges (zoom in and you will see) and we want them sharp. To do this Image / Adjustments / Posterise and drag the slider all the way to the left (value 2). Compare the first and second images to see the difference this step makes. [Midguard says] If you set the default interpolator to Nearest Neighbor, you can skip the posterization step. Preferences > General, Image Interpolation is the second option from the top. I believe it's set to Bicubic by default.
12. Use the crop tool to crop to the extents of the canvas (this gets rid of any chequerboard which is off the edge of the canvas which you can't see but will appear again if you decide to make your canvas bigger for any reason).
13. Duplicate the graticule layer (call the new layer neatline)
14. Hide the neatline layer and run a find edges filter on the graticule layer (filter / stylise / find edges). Magic wand, select the white and delete. This leaves you with a graticule with 2 px wide lines. [Midgard says] To reduce the graticule to 1px lines, right after you delete the white, use the arrow keys to nudge the selection up 1px and delete, then nudge 1px to the left and delete, then nudge it 1px down and delete. If the graticule is too overpowering, reduce the opacity of the layer.
15. Make the stroke layer active and magic wand select the solid colour, make the neatline layer active and hit delete to leave the neatline frame.
16. Using the current selection, Edit / Stroke 2 px to make the inside border of the frame.
17. Select all, Edit / Stroke 2 px (inside radio button checked) to make the outside border of the frame.