Similar, but not identical problem here.  It seems to happen mainly when Skype has been idle for some time, when someone sends me a chat message everything hangs for up to five minutes.

Software:
  Ubuntu Dapper running:
    Kernel 2.6.15-27-amd64-k8
    Skype 1.3.0.53_API installed in a 32-bit chroot from .deb package on skype.com
    Proprietory ATI (fglrx) modules
Hardware:
  Acer Ferrari 4005WLMi with:
    AMD Turion 64 CPU
    1GB RAM

Oct  9 09:48:14 localhost kernel: [175197.261996] BUG: soft lockup detected on CPU#0!
Oct  9 09:48:15 localhost kernel: [175197.262000] CPU 0:
Oct  9 09:48:15 localhost kernel: [175197.262002] Modules linked in: af_packet nfs lockd sunrpc hci_usb rfcomm hidp l2cap bluetooth ppdev fglrx powernow_k8 cpufreq_userspace cpufreq_stats freq_table cpufreq_powersave cpufreq_ondemand cpufreq_conservative video tc1100_wmi sony_acpi pcc_acpi hotkey dev_acpi container button acpi_sbs battery ac i2c_acpi_ec i2c_core nsc_ircc ipv6 dm_mod md_mod sr_mod sbp2 scsi_mod lp joydev tsdev irda bcm43xx pcspkr tg3 crc_ccitt parport_pc parport pcmcia snd_atiixp ieee80211softmac psmouse snd_atiixp_modem snd_ac97_codec snd_ac97_bus ieee80211 ieee80211_crypt serio_raw yenta_socket rsrc_nonstatic snd_pcm_oss snd_mixer_oss pcmcia_core snd_pcm snd_timer snd soundcore snd_page_alloc shpchp pci_hotplug evdev ext3 jbd ide_generic ehci_hcd ohci1394 ieee1394 ohci_hcd usbcore ide_cd cdrom ide_disk generic atiixp thermal processor fan capability commoncap vga16fb cfbcopyarea vgastate cfbimgblt cfbfillrect fbcon tileblit font bitblit softcursor
Oct  9 09:48:15 localhost kernel: [175197.262045] Pid: 9755, comm: skype Tainted: P      2.6.15-27-amd64-k8 #1
Oct  9 09:48:15 localhost kernel: [175197.262048] RIP: 0010:[hash_futex+207/256] <ffffffff801580df>{hash_futex+207}
Oct  9 09:48:15 localhost kernel: [175197.262056] RSP: 0018:ffff810008391da0  EFLAGS: 00000286
Oct  9 09:48:15 localhost kernel: [175197.262060] RAX: 000000003dfe6d17 RBX: ffff810008390000 RCX: 00000000dec8e9a9
Oct  9 09:48:15 localhost kernel: [175197.262063] RDX: 00000000e6fc00ff RSI: 0000000007bfcda2 RDI: ffff810008391eb8
Oct  9 09:48:15 localhost kernel: [175197.262066] RBP: 0000000000000202 R08: 000000000000006e R09: 0000000000000000
Oct  9 09:48:15 localhost kernel: [175197.262070] R10: ffff810008390000 R11: 0000000000000202 R12: ffffffffffffffef
Oct  9 09:48:15 localhost kernel: [175197.262073] R13: ffff8100395b6e40 R14: 0000000008cd4000 R15: 00000000ffffffea
Oct  9 09:48:15 localhost kernel: [175197.262078] FS:  00002aaaab7acce0(0000) GS:ffffffff8044a800(0063) knlGS:0000000059230bb0
Oct  9 09:48:15 localhost kernel: [175197.262081] CS:  0010 DS: 002b ES: 002b CR0: 000000008005003b
Oct  9 09:48:15 localhost kernel: [175197.262084] CR2: 0000000055576250 CR3: 00000000288f6000 CR4: 00000000000006e0
Oct  9 09:48:15 localhost kernel: [175197.262086]
Oct  9 09:48:15 localhost kernel: [175197.262087] Call Trace:<ffffffff801589bb>{do_futex+795} <ffffffff801433f3>{current_fs_time+67}
Oct  9 09:48:15 localhost kernel: [175197.262102]        <ffffffff80113d2a>{do_gettimeoffset_tsc+10} <ffffffff80163f74>{compat_sys_futex+212}
Oct  9 09:48:15 localhost kernel: [175197.262131]        <ffffffff80163a1a>{compat_sys_clock_gettime+106} <ffffffff80128743>{cstar_do_call+27}
Oct  9 09:48:15 localhost kernel: [175197.262143]