Hey Patrick,
Thanks again for your timely response your information has been very helpful in narrowing down the possible causes.
When I am in PageMaker if I go to Print-/Color-/CMS Setup
It brings me to a list of preferences for PageMakers CMS.
The one we have chosen will be in bold but Ill list some of the other types available
Color Management - OFF, on
Monitor Simulates - none, COMPOSITE printer, separations
New Items Use - NONE, Kodak ICC
Then it has KODAC ICC Settings
Monitor - GENERIC EBU 1.5 GAMMA, nec multisync 1.5 - 2.2, kodak sRGB display, generic p22 1.5 - 2.2 gamma
Composite Printer - CANON BJC-240, it has a list of some Canons (not including our Canon iR4080) and some Epsons, HP’s and Kodak options
Separations Printer - NEWGEN CHROMAX, same list
RGB Image Source - CANON BJC-240, then has some monitor options and EPSON/HP options
CMYK Image Src - NEWGEN CHROMAX, then same options and some TekPhaser ones.
It also gives me the option to click a box saying:
Embed profiles in documents,
Manage composites on printer
Use extra memory to improve performance
That is what appears in PageMaker for CMS. So as far as posible ICC profiles to use it only has Kodak ICC, and for composite/separations printer it doesnt even list our Canon ImageRunner c4080i.
You said if not showing up in a list you may need to go in UI and tell which kind of output your using… Does UI mean User Interface? 
…
So when I am in ILLUSTRATOR, I can chosose Document color mode CMYK or RGB (which one?)… Then when i go to print and Color Managment, I get a similar list of options:
Print Preset - CUSTOM, default, Print Preset 1
Printer - List of available printers
Color Management
Document Profile - Untagged CMYK (wont let me change this)
Color Handling - Let illustrator determine colors, or Let PostScript(wont let me choose that)
Printer Profile - sRGB IEC6 1966-2.1, and it gives me a list of printers including ours, and some monitors etc
Rendering Intent - Relative Colorimetric, Perceptual, Saturation etc
Anyways let me know what you think or if you need any more information…
Thanks again
Dan