I am not sure if you are using the "export" command to "attach" the image to the background.  If you are "combining objects with background" manually, before exporting, avoid that step.  Depending on your version, there may be an "Export for Web" or "Web Image Optimizer".  Both of these will bring up the .GIF dialogue boxes.  If you are using an older version, there is a more manual way of doing this, but will still bring up the .GIF dialogue box (unless it is really old).

For starters I reccomend saving your new logo as a .CPT file to begin with (if you ahvent already done so), that way you can always come back to this step before the export, incase something goes wrong.

In either case, assuming you are to the point of exporting as .GIF, you will have seen the prompt tell you that all images will be combined with background, and the background will most likely have changed color.  Continue through the dialogue boxes.  After the color options, and dithering, smoothing etc choices, a final option for .GIF is to set background transparency.  The easiest way is to have created a mask of the object, then you can select the mask for transparency.  Otherwise, you may have to set an obscure color for the background before you begin the export (preferably one completely outside the range of colors of your logo).  Then you can select that color to set as transparent.  If the background is a blended color, it may pick up some of the color in your logo as well.  That is why the mask option works best.

The easiest way to do this is to select your object, then create a mask from the object before starting your export.
Mask > Create > Mask From Object (depending on your version).

Hope this gets you pointed in the right direction.  Post back if this doesnt help.

I have photo-paint 9. I'm attempting to smooth out the rough edges of the logo. When I place it on the webpage you see the light pixels surronding the logo, also made in photo-paint. I can do two things, I can work on the logo and export it as GIF and during this process remove the background which works fine, or I can remove the background, work on the logo and attacht it to the background, in this case transparent, when I use the second method, the whole page turns blue, the color of the logo. I guess in short the problems is the light pixels on the edge of my logo which I have difficulty in removing via change color, rubbing out takes too long, and using the pixel feather I believe it's called to smooth out the edges between 1 and 5 pixels doesn't give me the desired result either. Hue, contrast, selective color, you name it there's always a part of the logo that remain lighter then the rest. Thanks for your time.

Well, got it, now the following problem, if I place the logo in large format it all looks fine, color is good and background transparent. However when I minimize the logo and place it, those light colored pixels on the edges return. You have any ideas how I can sole this problem. The logo is dark blue and with a dark background, when placing it on a light background there are no problems. Thanks, going nuts.

One of two ways to approach this.  The first is to make the background match the color of your web page.  This way is not as elegant if you change web backgrounds, or if you put it on various pages with different colors.

The second way would be a combination of things.
1.) make a second copy of your completed logo.  Make this a new object.  Sometimes pasting this object into a new layout can help with unwanted jaggies.  This can also help make your pallette selective - if you begin the new layout with an 8bit pallete.  Also, make sure your background has no variations onf the "blue" pallete - go with something with a very low blue content - something contrasty and opposite side of the color wheel - yellowish if I have to guess (but be careful of any whites). Possibly even something in the reds.

2.) when you export your gif, be sure to select the "optimized" or "adaptive" color pallete choices.  Both have had good luck for me in the past.

3.) When you create your mask around the object, try not to feather it, as this gives a semi transparent edge to the mask.  You would be better off with 0 transparency, and 0 feathering.  This gives a nice clean crisp edge.  If you can get away with it, you would be better off REDUCING the mask by 1 pixel (inside).  This will cut off the outter most layer of pixels from the mask, and cut your logo as close as possible to ensure no background "artifacts".

These tips should get you a much cleaner final output.  The biggest two things you can do is select a contrasting background color instead of no background, and get that logo object duplicated, and have a distinct background and a seperate logo.  This will help insure that the two are not blending somewhere along the line - especially with a transparent background - it can be hard to see any "smoothing" areas that the mask might pick up.

I am sorry I cant give you more precise directions, as I haven't used version 9 in so long now, it is hard to remember which options it had and which it didnt.  There are some good version 8, 9 and 10 tutroials on the web though.  Google Corel Photo paint tutorials, and you get a good list.  Here are a few:
http://www.huntfor.com/design/tutorials/photopaint.htm
http://www.visionary-voyager.com.au/corel/photopaint/

The reason I recommend these are they have specific directions of EXACTLY which menu/tool options to select.  Some of the techniques may be below you, but you can find the specifics here that might help.  
This last one (below) will be of particular benefit, since it goes over the details of gif images in depth.  However, I beleive this a version 8 tutorial, so there may be some slightly different methods of accomplishing the same tasks, as 9 had some pretty major changes over 8, but the theory will be the same.
http://www.visionary-voyager.com.au/corel/photopaint/web_works/webworks.htm

Let me know if there is anything else I can help you with.

I found one more thing that may help with those "artifacts"....

Even thought his is written for converting jpg to gif, the Smart Blur tool still might be of some help.
http://www.designertoday.com/Tutorials/PhotoPaint/1073/Corel.PhotoPaint.Tutorial.JPEG.to.GIF.aspx

Thanks for your time atrofy, I'll get to work with your suggestions this weekend and let you know how it worked out.
Thanks again.

Well spent several hours just going nuts, different methods, different possibilities and I just couldn't get rid of the white fringes. Found a good tutorial over white fringes and a transparent backgrounds http://www.wise-women.org/tutorials/ps1/ so I'll try that this evening in photo shop. However I surely wish to thank you greatly for your time and work, seems I've finally found what I'm looking for.