Salute Arch,
I have written this reply about 3 times now

I hope I dont sound condensending as that is not my intent. I dont know your level of expertise with graphics in different enviornments (Raster graphics vs. Vectored graphics.) It sounds like you are reaching the limits of rasterization at the actual needed size of your graphic.
Raster:
The nature of a raster graphic (Photoshop) is the use of colored pixels working together to produce output, when viewed, that generates an overall impression. When you get into the 1 or 2 pixel size at actual, you lose detail. An example of this is when you magnify a Rastered graphic, it blurs and looks unsavory. The more you resize a Raster (up or down) the detail starts to dwindle.
Vector:
The nature of a Vectored graphic (Illustrator, Freehand, ect.) is a series of mathematical lines that are given assignment to the graphic. No matter how much you resize a Vector, the mathematical assignment of the lines do not change. The graphic is just as clear (or crisp) no matter the final output size.
Now, the problem skinners run into is that no matter the source we use to create our skins, the final output MUST be rastered (8x indexed bitmap.) There is no single technique that will allow you to have a perfectly crisp graphic (in your case, the noseart) at the end item size you require. Some detail is going to be lost due to the final rastering of the skin. I will optimize my nosearts as much as I can, but a lot of the time the noseart has to be balanced at the reduced size to give the "illusion" of being crisp. Now this isnt necessarily the case with the particular graphic you are talking about. Being the graphic is handpainted line-art, at that particular size, I would do it like this...
Step 1.
Using a vectoring program, I would create the graphic at a larger than needed size, say 256x256. Being the final output size is so small, I would only use the primary color (in this example..red) with no outline color. Once the graphic is created, I would export that vectored graphic as a .tif format.
Step 2.
Now that I have my .tif, I would open it in Photoshop. Once opened in Photoshop, remove the white background that surrounds the lineart. The easy way to do this is to use a Photoshop plug-in called "remove white." You can find that at Simmerspaintshop.com. Once all white is removed, select all. Copy, create new document with a transparent background, paste. Save new document as a .png with alpha transparency.
Step 3.
Open your original skin .psd and find the "end size" you need the lineart to be. I generally do this by using the square marquee, drawing the marquee on the skin in the position and size needed. Select the background layer, then edit/copy. Create new document. This will give you the final dementions the lineart needs to be. Press cancel as you dont need this new document, you only needed the size.
Step 4.
Using the transparent .png, resize it using the navigator box window. This is done by pressing the "-" (minus) button on the left of that box window. It will give you an immediate feedback on what that graphic will look like at that size you reduced to. If it looks blocky, click filter/blur/gaussian blur. Only base your adjustments for every 25% of minimization. For example, 50% will look good. However, 66.7% will look bad. Use small increments of adjustment in the blur menu. If it still looks good, but still too large, do the same thing again. Reduce, blur, ect. Once at the size you feel is right, and crispness you feel is right...press the print screen button on your keyboard.
Step5.
Ceate new document. Edit/Paste. Using the square marquee again, select only the borders of the lineart (it will be at the reduced size you did by using the navigator window. Edit/Crop. You now will only have the lineart selected with a white background. Use "remove white" again or Select all. Using the Magic Wand tool, press and hold the Alt key. Select the outside white borders of the lineart. Once all selected, you will see that only the lineart itself has the "dancing ants" from the marquee. Using the arrow keys on your keyboard, move the lineart up one pixel, then back down 1 pixel to the original place. Edit/Copy. Create new document. Paste.
You should now have the new lineart at correct size and crispness. Just copy that layer with the graphic on it and paste it into your skin. Resize or do any fine tuning needed and you should be good. Make sure that you are not indexing your final work for test by using the Photoshop plugin for indexing. You should use a 3rd party utility like "Bright", also found at Simmerspaintshop.
This is just a generalization of how I do it bud. Your mileage may vary

Hope this helped point you in a direction you hadn't thought of.
ReDhAwK