I'm using Ubuntu 9.04 (upgraded from 8.10) and have the same problem.
No kpresenter-data package is installed, but krita-kde4 ("upgraded" from krita 1.x) fails to start, too.

***@Gremlin:~$ krita
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 0 CFGSimplification
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 1 IPConstantPropagation
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 2 InstructionCombining
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 3 CFGSimplification
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 4 TailDuplication
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 5 CFGSimplification
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 6 InstructionCombining
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 7 Reassociate
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 8 InstructionCombining
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 9 TailCallElimination
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 10 CFGSimplification
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 11 LICM
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 12 InstructionCombining
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 13 IndVarSimplify
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 14 LoopUnroll
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 15 InstructionCombining
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 16 LoadValueNumbering
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 17 GCSE
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 18 SCCP
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 19 InstructionCombining
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 20 DeadStoreElimination
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 21 AggressiveDCE
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 22 CFGSimplification
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 23 ConstantMerge
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 24 CFGSimplification
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 25 PromoteMemoryToRegister
GTLCore (Debug): in Optimiser_p.cpp at 111 in GTLCore::Optimiser::Private::setLevel: 26 InstructionCombining
GTLCore (Debug): in Type.cpp at 104 in GTLCore::Type::Type: Create type for 0
GTLCore (Debug): in Type.cpp at 104 in GTLCore::Type::Type: Create type for 1
GTLCore (Debug): in Type.cpp at 104 in GTLCore::Type::Type: Create type for 2
GTLCore (Debug): in Type.cpp at 104 in GTLCore::Type::Type: Create type for 3
GTLCore (Debug): in Type.cpp at 104 in GTLCore::Type::Type: Create type for 4
GTLCore (Debug): in Type.cpp at 104 in GTLCore::Type::Type: Create type for 5
GTLCore (Debug): in Type.cpp at 104 in GTLCore::Type::Type: Create type for 6
GTLCore (Debug): in Type.cpp at 104 in GTLCore::Type::Type: Create type for 7
GTLCore (Debug): in Type.cpp at 104 in GTLCore::Type::Type: Create type for 8
GTLCore (Debug): in Type.cpp at 104 in GTLCore::Type::Type: Create type for 9
GTLCore (Debug): in Type.cpp at 104 in GTLCore::Type::Type: Create type for 10
GTLCore (Debug): in Type.cpp at 104 in GTLCore::Type::Type: Create type for 11
GTLCore (Debug): in Type.cpp at 104 in GTLCore::Type::Type: Create type for 14
krita(7321) KServiceFactory::findServiceByDesktopPath: "findServiceByDesktopPath: kritapart.desktop not found"
krita(7321) KServiceFactory::findServiceByDesktopPath: "findServiceByDesktopPath: Office/krita.desktop not found"


Regards,
Nameless