I see the same message for my ATI Technologies Inc Radeon R200 QL [Radeon 8500 LE] on Ubuntu 10.04 while playing World of Padman. The game exits with the message:

drmRadeonCmdBuffer: -22. Kernel failed to parse or rejected command stream. See dmesg for more info.

Also dmesg shows this:

[135106.802528] ------------[ cut here ]------------
[135106.802571] WARNING: at /build/buildd/linux-2.6.32/arch/x86/kernel/apic/ipi.c:109 default_send_IPI_mask_logical+0xb2/0xf0()
[135106.802586] Hardware name: -[622140U]-
[135106.802591] empty IPI mask
[135106.802600] Modules linked in: autofs4 binfmt_misc nfsd exportfs nfs lockd nfs_acl auth_rpcgss cx88_blackbird cx2341x tda827x tda8290 fbcon tileblit font bitblit softcursor snd_intel8x0 vga16fb vgastate tuner snd_ac97_codec cx88_alsa ac97_bus snd_pcm_oss snd_mixer_oss snd_pcm cx8802 cx8800 snd_seq_dummy arc4 cx88xx radeon pc87360 v4l2_common rt2500pci ttm snd_seq_oss rt2x00pci videodev ir_common snd_seq_midi rt2x00lib snd_rawmidi drm_kms_helper snd_seq_midi_event led_class tveeprom v4l1_compat snd_seq videobuf_dma_sg mac80211 drm btcx_risc snd_timer i2c_algo_bit snd_seq_device cfg80211 snd e7xxx_edac eeprom_93cx6 w83791d hwmon_vid videobuf_core soundcore snd_page_alloc edac_core i2c_i801 sunrpc ppdev intel_agp psmouse shpchp serio_raw agpgart parport_pc lp parport usbhid hid usb_storage floppy tg3
[135106.802866] Pid: 17, comm: events/2 Not tainted 2.6.32-22-generic #33-Ubuntu
[135106.802871] Call Trace:
[135106.802895]  [<c014c3d2>] warn_slowpath_common+0x72/0xa0
[135106.802905]  [<c0120952>] ? default_send_IPI_mask_logical+0xb2/0xf0
[135106.802913]  [<c0120952>] ? default_send_IPI_mask_logical+0xb2/0xf0
[135106.802925]  [<c014c44b>] warn_slowpath_fmt+0x2b/0x30
[135106.802934]  [<c0120952>] default_send_IPI_mask_logical+0xb2/0xf0
[135106.802956]  [<c011edb1>] native_send_call_func_ipi+0x41/0x60
[135106.802969]  [<c017c298>] smp_call_function_many+0x148/0x1c0
[135106.802983]  [<c012c730>] ? __change_page_attr_set_clr+0x60/0x1c0
[135106.802999]  [<c012bf90>] ? __cpa_flush_range+0x0/0x30
[135106.803007]  [<c012bf90>] ? __cpa_flush_range+0x0/0x30
[135106.803024]  [<c017c334>] smp_call_function+0x24/0x30
[135106.803035]  [<c0152cff>] on_each_cpu+0x1f/0x50
[135106.803046]  [<c012cb81>] change_page_attr_set_clr+0x2f1/0x3b0
[135106.803053]  [<c012cd77>] _set_memory_wb+0x37/0x40
[135106.803070]  [<c012cd9d>] set_memory_wb+0x1d/0x50
[135106.803077]  [<c012cde7>] set_pages_wb+0x17/0x20
[135106.803111]  [<f85e4221>] ttm_tt_set_caching+0x61/0x1e0 [ttm]
[135106.803142]  [<f803406e>] ? agp_free_memory+0x9e/0x120 [agpgart]
[135106.803164]  [<f85e43c9>] ttm_tt_free_alloced_pages+0x29/0xb0 [ttm]
[135106.803187]  [<f85e4917>] ttm_tt_destroy+0x37/0x90 [ttm]
[135106.803203]  [<f85e4fe9>] ttm_bo_release_list+0x59/0xb0 [ttm]
[135106.803223]  [<f85e4f90>] ? ttm_bo_release_list+0x0/0xb0 [ttm]
[135106.803242]  [<c034cb3d>] kref_put+0x2d/0x60
[135106.803260]  [<f85e5f0e>] ttm_bo_delayed_delete+0x8e/0xe0 [ttm]
[135106.803274]  [<f85e5f78>] ttm_bo_delayed_workqueue+0x18/0x30 [ttm]
[135106.803291]  [<c016369e>] run_workqueue+0x8e/0x150
[135106.803310]  [<f85e5f60>] ? ttm_bo_delayed_workqueue+0x0/0x30 [ttm]
[135106.803323]  [<c01637e4>] worker_thread+0x84/0xe0
[135106.803344]  [<c0167740>] ? autoremove_wake_function+0x0/0x50
[135106.803353]  [<c0163760>] ? worker_thread+0x0/0xe0
[135106.803364]  [<c01674b4>] kthread+0x74/0x80
[135106.803382]  [<c0167440>] ? kthread+0x0/0x80
[135106.803392]  [<c0104087>] kernel_thread_helper+0x7/0x10
[135106.803399] ---[ end trace c6c9aa9009c05328 ]---
[136210.792945] [drm:r100_cs_track_texture_check] *ERROR* No texture bound to unit 1
[136210.792952] [drm:radeon_cs_ioctl] *ERROR* Invalid command stream !
[136258.585336] [drm:r100_cs_track_texture_check] *ERROR* No texture bound to unit 1
[136258.585343] [drm:radeon_cs_ioctl] *ERROR* Invalid command stream !
[191097.125339] [drm:r100_cs_track_texture_check] *ERROR* No texture bound to unit 1
[191097.125346] [drm:radeon_cs_ioctl] *ERROR* Invalid command stream !