Does bump mapping even work when the texture resolution is the same as the vertex resolution?
Normal mapping has nothing at all to do with how many vertices there are. Normal mapping is a per-pixel operation, the best normal map resolution is the one that most closely matches how many pixels the model takes up on the screen. If your screen size is 1024x1024 and your model takes up 1/4 of the screen, then you should use a normal map that is 512x512. If the normal map is heavily blurred then you can use a smaller resolution with out much noticeable decrease in apparent detail.
The idea of normal mapping is to fill in the space between vertices, with the illusion of detail. This makes a low-poly model look like a high-poly model. This illusion breaks down at the silhouette of a model and also at steep angles.
If you use very small textures then those textures will be sampled up in size for models that take up a lot of screen space, this will result in blocky artifacts.
To clear up those seam edges you will likely have to make the textures seamless.
I Googled -> how to make seamless textures and chose a couple to get you started.
Also, I suppose I should also mention. The PhotoShop tutorial and the GIMP tutorial are using two very different methods to achieve seamless-ness.
The GIMP method is more of an optical illusion created by a plugin. However, the method used on the PhotoShop page will work in GIMP as well, both have the offset function. It's just that GIMP also has a quick and dirty plugin trick that may work for many circumstances.